Abstract: The main challenge in using fiber-reinforced cementitious composites (FRCC) in cold regions is that the materials’ crack resistance and mechanical strength drop sharply in ultra-low temperatures, and the main factors causing this are still unclear. This study compares four types of organic fibers—POM, PVA, PP, and HDPE—systematically testing how their strength degrades in extreme cold, the macro mechanical performance of specimens, and fiber-matrix pullout behavior, combined with microscopic structure analysis, to clarify the main mechanisms behind strength loss. The results show that FRCC strength degradation under ultra-low temperatures is due to a combination of factors: the weakening of fiber properties, interfacial debonding, and matrix brittleness. The degree of decline varies significantly between fibers. For example, POM fibers saw a 54.09% and 27.20% reduction in flexural and compressive strength compared to regular mortar, but their intrinsic strength only dropped by 14.75%, which is much lower than the other fibers. They also had high ultimate bond strength and pullout work, indicating the best structural stability. Based on this, in FRCC structures operating in cold regions, using cost-effective POM fibers should be prioritized to effectively control low-temperature cracking and strength failure. When selecting materials, attention should be paid to the low-temperature durability and intrinsic strength of fibers. This study provides data support and theoretical guidance for the selection, design, and application of fiber-reinforced cementitious materials in cold regions.