Frost weathering of porous materials caused by seasonal temperature changes is a major source of damage to the world's infrastructure and cultural heritage. Here we investigate poly(vinyl alcohol) (PVA) addition as a means to enhance the freeze-thaw durability of concrete without compromising its structural or mechanical integrity. We evaluate the ice recrystallization inhibition activity of PVA in a cementitious environment and the impact of PVA on key structural and mechanical properties, such as cement hydration (products), microstructure, strength, as well as freeze-thaw resistance. We find that a low amount of PVA significantly reduces the surface scaling of concrete and displays excellent ice recrystallization inhibition in the saturated Ca(OH)2 solution, which has a similar pH value as cement pore solution, while it does not affect cement hydration, microstructure, nor its mechanical properties. These findings contribute to new insights on the freeze-thaw damage mechanism, and more importantly, we disclose a new direction for the design of concrete with excellent freeze-thaw resistance.