Abstract: To address the shrinkage cracking and insufficient strength of conventionally cement-solidified red sandstone soil under artificial freezing, this study proposes an epoxy resin–cement composite solidification method. Orthogonal and response surface experiments, along with unconfined compression tests (UCT) and microscopic analyses (XRD, SEM, NMR), were performed to evaluate the effects and interactions of cement content, epoxy resin content, and low-temperature environment on the mechanical behavior of the treated soil. Results indicate that the composite solidification substantially suppresses cracking at low temperatures, increases unconfined compressive strength by 230%~680% relative to untreated soil, and transforms the failure mode from brittle fracture with through-going cracks to ductile shear failure. The dominant factors affecting strength, in descending order, are epoxy resin content (positively correlated), cement content (exhibiting an initial increase followed by a decrease), and low temperature. Microscopically, total porosity is reduced by up to 68.4%, while maximum crack width and crack area ratio decrease by 83.7% and 87.2%, respectively. Epoxy resin effectively fills pores, enhances interfacial toughness, and forms an organic–inorganic interpenetrating network with cement hydration products, synergistically reducing porosity and improving soil compactness. This study provides a theoretical and technical basis for applying composite solidification to red sandstone soil in artificial freezing engineering contexts, such as foundation pits and tunnels.