Carbon-capture-and-storage (CCS) is an important technology to reduce CO2 emissions. A commercial method to establish the CCS on a large scale is to sequestrate CO2 in depleted oil reservoirs and to combine it with enhanced oil recovery (EOR) operations. In this way, the CO2 emission is reduced, as well as the oil production increases. The joint CCS-EOR planning problem determines the optimum allocation of existing CO2 to depleted reservoirs and the scheduling of the EOR operations. This paper presents a deterministic MIP model which is a modification of an existing model in the literature. Then, this model is extended to a two-stage stochastic model in which the parameters expressing the initial oil yields and the periodic depletion factor of oil yields associated with reservoirs are uncertain, and the uncertainty is realized as soon as the operation of the reservoir is started. Our stochastic model is computationally more efficient than the existing model in the literature, due to the reduction of binary variables, as well as the absence of “non-anticipativity constraints”. Instead, our stochastic model is less realistic. The proposed models are examined over two case studies taken from the literature. The obtained results confirm the higher effectiveness of our stochastic model.