Abstract: The poor water resistance of magnesium oxychloride cement (MOC) is a significant drawback with far-reaching consequences, particularly affecting its frost resistance. This limitation has become a major obstacle to its widespread use in plateau areas, where harsh environmental conditions prevail, such as large temperature differences between day and night and frequent freeze–thaw cycles. MOC’s low frost resistance makes it unsuitable for long-term, stable use in these areas. To address this issue and expand MOC’s applicability in plateau areas, an innovative approach was adopted. Magnesium chloride was coproduced from salt lake and highland barley straw ash (HBSA) to prepare MOC. The unique properties of HBSA were expected to enhance the performance of MOC. Subsequently, MOC mortar (MOCM) with different HBSA content was carefully prepared. A series of tests were conducted to understand HBSA’s impact on frost resistance. The damage deterioration evaluation index was used to objectively assess the damage MOCM suffered under freeze–thaw erosion conditions, providing crucial data on performance changes. At the same time, the apparent morphology of MOCM in freeze–thaw erosion environments was analyzed to gain a more intuitive understanding of how the material degraded. Moreover, the pore structure of MOCM was tested using multiple methods. Water absorption tests measured its capacity and inferred pore characteristics. Low-field nuclear magnetic resonance (LF-NMR) accurately analyzed internal pore distribution, while the gas adsorption method (BET) provided detailed information about specific surface areas and pore size distribution. Scanning electron microscopy (SEM), X-ray diffraction (XRD), and thermogravimetric (TG) testing characterized the microstructure and phase composition of MOC, revealing the internal reasons for HBSA’s influence on frost resistance. The results were remarkable. MOCM with a mass fraction of 10% HBSA showed a 23.21% increase in frost resistance compared to MOCM without HBSA. After 60 freeze–thaw cycles, the open porosity of MOCM doped with a mass fraction of 10% HBSA decreased by 2.11%. What’s more, the proportion of harmless pores and less harmful pores increased by 59.28%, while harmful pores decreased by 25.76%. The most effective pore size also decreased, indicating a more refined pore structure. Furthermore, a significant amount of M–S–H gels formed in the hydration products of MOCM, enhancing microstructure compactness and stabilizing the 5-phase crystal, thereby effectively improving frost resistance.