The freezing method is widely used in the construction of vertical shafts in water-rich strata. The formed frozen rock wall is often involved in the creep process, and in particular, the creep behavior of frozen fissured rock mass poses a great threat to construction safety. To better understand the creep instability law of ice-filled, fractured red sandstone under freezing and triaxial stress conditions, a series of triaxial creep tests on frozen red sandstone specimens containing a single, pre-existing flaw at −10°C and under a confining pressure of 4 MPa were carried out with a self-developed DRTS-500 subzero rock triaxial testing system. The multistage loading creep curves were obtained, and the evolution laws of deformation and damage for the frozen specimens in the primary (instantaneous), secondary (steady-state) and tertiary (accelerating) phases were analyzed. The nonlinear visco-elastoplastic constitutive model of red sandstone with a single ice-filled flaw was established according to the fractional calculus theory and the Kachanov damage theory. The results show that the initial creep property, unstable creep property and creep failure mode of frozen single-flaw red sandstone are significantly affected by the flaw dip angle. The proposed creep damage model can accurately describe the complete creep curves of frozen red sandstone with a single ice-filled flaw, especially in the unstable creep stage. The influences of the stress level and flaw dip angle on the creep parameters were analyzed, and sensitivity analyses of the characteristic creep parameters were carried out to verify the reliability and rationality of our creep model. This research can be applied to the assessment of collapse, cracking and other long-term failures and hence can be used as a theoretical basis of design in the freezing engineering of coal mine shafts.