Experimental findings pertaining to the frost resistance of calcium sulfoaluminate (CSA) and amorphous calcium aluminate (ACA) cement-based repair mortars incorporated with anhydrite gypsum are described herein. To prepare the mortars, CSA and/or ACA cements were used as binders, and the water–binder ratio was fixed at 0.57. The compressive and bond strengths, chloride-ion penetration resistance, and scaling resistance of the mortars were measured. Based on the ASTM C666 method, the resistance to both frost action and multi-deterioration of chloride and frost attacks on the mortars were experimentally examined. Calcium aluminate-based binders effectively enhanced the compressive and bond strengths of the mortars owing to the formation of C2AH8 and Ye’elimite hydrates. Furthermore, replacing 25% ACA with OPC yielded excellent resistance to both frost attack and multi-deterioration of chloride and frost attacks. Replacing ACA at an appropriate level as a binder effectively improves the durability of concrete road facilities in winter.