This Article addresses the problem of optimizing the investment planning process of a logistics infrastructure for the distribution of petroleum products under uncertainty. For this purpose, a two-stage stochastic model was developed. Because of the large number of possible scenarios for the future realization of demands, the Sample Average Approximation (SAA) methodology was used to produce approximations of the optimal solution. The proposed model and solution methodology were applied to a real case study on the distribution of petroleum products in northern Brazil. The results show that the methodology allows us to obtain solutions that are relatively close to the real optimal solution of the problem with optimality gaps estimated at up to 1%, which are reasonable for most practical purposes.