A carbon capture and storage (CCS) plays a very important role to reduce CO2 dramatically in CO2 emission sources which are distributed throughout various areas. Numerous research works have been undertaken to analyze the techno-economic feasibility of planning the CCS infrastructure. However, uncertainties such as CO2 emissions, CO2 reduction costs, and carbon taxes may exist in various impact factors of the CCS infrastructure. However, few research works have adopted these uncertainties in designing the CCS infrastructure. In this study, a two-stage stochastic programming model is developed for planning the CCS infrastructure under uncertain operating costs and carbon taxes. It can help determine where and how much CO2 to capture, store or transport for the purpose of minimizing the total annual CO2 reduction cost in handling the uncertainties while meeting the CO2 mitigation target. The capability of the proposed model to provide correct decisions despite changing the operating costs and carbon taxes is tested by applying it to a real case study based on Korea. The results will help to determine planning of a CCS infrastructure under uncertain environments.