Quality of interfacial bond between fibers and matrix determines the post-cracking behavior of fiber-reinforced composites. Fatigue-induced interface deterioration between fibers and matrix has not been investigated systematically which prevents understanding of premature failure of fiber-reinforced composites subject to fatigue. This study experimentally investigated the deterioration mechanism of flexible fibers in brittle matrix subject to fatigue load. Specifically, the effect of fatigue-induced deterioration of interface between micro-PVA fiber and cement matrix was studied through the single fiber fatigue pullout tests and the micro-structural deterioration mechanism of the fiber-matrix interface under fatigue load was unveiled. It was found that fatigue load leads to fiber debonding which can be described by an empirical relation similar to the Paris' law. Fatigue-induced interface hardening can occur during fiber debonding stage as well as fiber slippage stage. Oil-treatment on surface of micro-PVA fiber was demonstrated as a mean to mitigate such fatigue-induced interface hardening.