Natural fiber reinforcement effectively mitigates strength degradation in soils subjected to freeze-thaw cycles. Although natural fiber-soil interfacial strength plays a crucial role in controlling the behavior of fiber-reinforced frozen soils, the mechanisms underlying its evolution under freeze-thaw conditions are not yet fully understood. This study investigates straw fiber-soil interfacial strength using fiber pull-out tests, scanning electron microscopy tests, and nuclear magnetic resonance tests conducted after 0, 1, 3, 5, 10, 15, and 20 freeze-thaw cycles. The results show that interfacial strength decreases exponentially as the number of freeze-thaw cycles increases. This reduction is more pronounced at higher water contents or greater dry densities, primarily due to its positive correlation with pore development induced by freeze-thaw processes. Additionally, a calculation method is proposed for determining the critical straw fiber length in fiber-reinforced frozen soils, providing theoretical guidance for engineering applications in cold regions.