• Tensile fatigue under repeated two-level block loading is first studied, representing simplified service loading. • Partial recovery of deformation and stiffness during the lower stress cycles is first identified, analogous to damage-retardation mechanism in steels. • Fatigue cycles below the constant amplitude fatigue limit can be damaging. The tensile fatigue behavior of Ultra-High-Performance Fiber-Reinforced-Cementitious Composites (UHPFRC) is critical for the long-term performance of UHPFRC structures, yet its response under variable amplitude loading remains unexplored. This paper experimentally investigates the tensile fatigue behavior of UHPFRC under two-level block loading, representing a simplified form of realistic structural loading histories. Six specimens were tested after being statically preloaded to a tensile strain of 1.5‰, representative of typical maximum strain in structural applications. Prior to fatigue testing, the local fiber volume and orientation of each specimen were quantified. Fatigue loading consisted of stress cycles both below and above the theoretical constant amplitude fatigue limits, while specimen responses were monitored using digital image correlation and displacement transducers. It was found that local fiber orientation governs both fatigue deformation and fracture location. The evolution of global deformation followed three stages: an initial rapid increase, a prolonged phase of gradual growth, and an accelerated and unstable increase leading to fracture. In the first and middle stages, deformation growth and specimen stiffness degradation were contributed primarily by the higher stress cycles. During the middle stage, partial recovery of deformation and stiffness occurred during the lower stress cycles, a behavior identified for the first time in UHPFRC and analogous to damage-retardation mechanisms reported in steel, which likely contributed to enhanced fatigue resistance. In the final stage, both lower and higher stress cycles contributed to strain accumulation, showing that stress cycles below the constant amplitude fatigue limit can also be damaging.