This paper reports the durability performance of non-air-entrained engineered cementitious composites (ECC) when subjected to freezing and thawing cycles. ECC is a newly developed, high-performance, fiber-reinforced, cementitious composite with substantial benefits both in terms of high ductility under uniaxial tensile loading and improved durability due to intrinsically tight crack width of less than 100 μm. To evaluate the frost durability of ECC, freezing and thawing testing in accordance with ASTM C666 Procedure A was conducted. The mass loss, pulse velocity change, and flexural parameters (ultimate deflection and flexural strength) of specimens subjected to freezing and thawing cycles were determined in the test. In addition, air-void parameters, in accordance with ASTM C457, modified point count method, and pore size distribution obtained by mercury intrusion porosimetry technique were studied. To analyze the influence of micro-fibers and high tensile strain capacity on the freezing and thawing durability of ECC, all of the above-mentioned properties were also investigated for a control ECC matrix (ECC without fibers). After 210 cycles of freezing and thawing, the control ECC matrix specimens were severely deteriorated, requiring removal from the test, but still exhibited better performance than the conventional non-air-entrained concrete, which would fail at much earlier cycles. On the other hand, ECC with fibers without air-entrainment had excellent resistance to cycles of freezing and thawing with minimal reduction in ultimate tensile strength and ductility. The observed superior frost durability of ECC over control ECC matrix in terms of lower weight loss, pulse velocity change, and higher flexural load and ductility can be attributed to the following reasons: Increase of pore volume larger than approximately 0.30 μm in diameter, intrinsically high tensile ductility and strength due to the presence of micro-poly-vinyl-alcohol fibers.