Cemented paste backfill (CPB) is a novel cementitious construction material that is used extensively for underground mine support and/or mine waste management worldwide. CPB consists of a mix of tailings (mine waste), water, and binder. In other words, tailings are transformed into construction materials. Key engineering properties required for the geotechnical design of CPB structures include strength and deformation behavior. However, there is a paucity of technical data and information about the effect of sub-zero temperatures on these properties. This paper presents an experimental study that focuses on the investigation of the influence of sub-zero curing temperatures on the strength, deformation behavior, and microstructure (e.g., pore structure, porosity, and binder hydration products) of CPB. Several CPB samples with various combinations of compositions (e.g., binder type, cement amount, and water content) cured at different temperatures (sub-zero and room temperatures) and times (7-90 days) are tested with regard to strength, stress-strain behavior, and microstructural characteristics. It is found that frozen CPB (FCPB) exhibits remarkable strength compared with unfrozen CPB and has a great resemblance to frozen soil. No obvious peak stress is observed from FCPB samples during compression, and strain hardening phenomena are commonly seen after the initial yield point. Factors that may affect the behavior of FCPB are thoroughly examined. Binder contents and types are found to be irrelevant; in contrast, water content plays a dominant role. This negligible effect of binder on the properties of FCPB is due to the inhibition of the binder hydration by sub-zero curing temperatures. FCPBs show coarser pore structure than unfrozen CPBs. The results obtained in this study have significant practical engineering applications for mines located in permafrost or cold regions. (C) 2021 American Society of Civil Engineers.