An important decision for policy makers is selecting strategic petroleum reserve sites. However, policy makers may not choose the most suitable and efficient locations for strategic petroleum reserve (SPR) due to the complexity in the choice of sites. This paper proposes a multi-objective programming model to determine the optimal locations for China’s SPR storage sites. This model considers not only the minimum response time but also the minimum transportation cost based on a series of reasonable assumptions and constraint conditions. The factors influencing SPR sites are identified to determine potential demand points and candidate storage sites. Estimation and suggestions are made for the selection of China’s future SPR storage sites based on the results of this model. When the number of petroleum storage sites is less than or equals 25 and the maximum capacity of storage sites is restricted to 10 million tonnes, the model’s result best fit for the current layout scheme selected thirteen storage sites in four scenarios. Considering the current status of SPR in China, Tianjin, Qingdao, Dalian, Daqing and Zhanjiang, Chengdu, Xi’an, and Yueyang are suggested to be the candidate locations for the third phase of the construction plan. The locations of petroleum storage sites suggested in this work could be used as a reference for decision makers.