The energy sector has dominated the world attention as recently arrived shale gas and slumping crude oil prices globally affect Petroleum Supply Chains (PSC). Fluctuating demand and prices are forcing companies to rethink existing distribution networks and production plans in order to improve network flexibility and cost efficiency. The current paper addresses this problem and presents a stochastic mixed integer linear program (MILP) for PSC design and planning under demand uncertainty that maximizes the expected net present value (ENPV) of a multi-entity multi-product PSC network. The decisions include locations, capacities, transport modes, routes, product affectations, inventories and fair-price costs and tariffs with economies of scale. The stochastic MILP designs a grassroots network with demand uncertainty for the Portuguese PSC, drawing important insights and research directions.