This work investigated the effect of adding ceria-stabilized tetragonal zirconia (Ce-TZP) on the fatigue behavior of alumina-based ceramic composites. Alumina powder (control group) and mixtures containing 5 wt.% (group A) and 20 wt.% (group B) of a commercial m-ZrO2/Al2O3/CeO2 powder mixture were milled/homogenized, compacted, sintered at 1600°C-2h, and submitted to hydrothermal degradation. The samples were characterized by relative density, microstructure, crystalline phases, and static mechanical properties. The cyclic fatigue strength was determined using the modified staircase method in 4-point bending tests. The results indicate that adding the m-ZrO2/Al2O3/CeO2 powder mixture to the Al2O3-matrix increases the tetragonal-ZrO2 grains (Ce-TZP) content, presenting 2.9 wt.% of Ce-TZP and 11.9 wt.% of Ce-TZP for group A and group B, respectively. Furthermore, the addition of Ce-TZP improves densification (98.5% → 99.1%) with a slight reduction in hardness and modulus of elasticity and a significant KIC increase of the composite (KIC = 6.7 MPa.m1/2, group B) when compared to monolithic alumina (KIC=2.4 MPa.m1/2). The fatigue strength limit of the control group was around 100 MPa, while the composites (groups A and B) presented the values of 279 MPa and 239 MPa, respectively. The results indicated that the incorporation of Ce-TZP significantly improves the fracture toughness of alumina-based ceramics. On the other hand, regarding the fatigue behavior, there was an increase in fatigue resistance in group A, resulting from the benefits of the t→m Ce-TZP grains transformation, which occurs during cyclic loading, producing a zone shielding that involves the tip of the crack, slowing its growth. The increase in the amount of Ce-TZP (group B) leads to an increase in the internal residual stresses between the phases due to anisotropy and difference in the thermal expansion coefficients, which accelerates the phase transformation and formation of microcracks at grain boundaries, reducing the fatigue strength of composites of group B.