This paper presents an experimental study that was conducted to clarify the effect of reinforcing short fiber characteristics such as the length, tensile strength, and adhesion on the frost resistance of fiber reinforced cementitious composites (FRCCs) by incorporating two types of polyvinyl alcohol (PVA) fibers and polypropylene (PP) fiber. FRCCs with a 1.5% volume ratio of fiber were investigated for frost resistance under freeze–thaw action of 300 cycles and were compared with non-fiber reinforced cementitious composite (Plan) specimens. The air void characteristics of mixtures were also investigated by mercury intrusion porosimetry (MIP), linear transverse method, and scanning electron microscope (SEM) images. The difference of the fiber type (PVA and PP) characteristics was affected by the dispersion of blended fibers in FRCCs and by the adhesion performance between the cementitious matrix and the fibers in the microstructure. Hence, the results of the compressive behavior indicated that the PVA FRCC specimens have superior resistance on the reduction of the compressive strength before and after freeze–thaw cycling compared to PP FRCC and Plain specimens. Additionally, the test results of the relative dynamic elastic modulus and mass loss indicated that the PVA FRCC specimens remain durability after freeze–thaw action of 300 cycles compared with virgin specimens. Therefore, the results of freeze–thaw tests revealed that the blending of PVA fibers to FRCC is considerably effective for frost resistance.