Fatigue refers to the changes in material properties caused by repeatedly applied loads. It has been widely studied for, e.g., construction materials, but much less has been done on soft materials. Here, we characterize the fatigue dynamics of a colloidal gel. Fatigue is induced by large amplitude oscillatory stress (LAOStress), and the local displacements of the gel are measured through high-frequency ultrasonic imaging. We show that fatigue eventually leads to rupture and fluidization. We evidence four successive steps associated with these dynamics: (i) the gel first remains solid, (ii) it then slides against the walls, (iii) the bulk of the sample becomes heterogeneous and displays solid-fluid coexistence, and (iv) it is finally fully fluidized. It is possible to homogeneously scale the duration of each step with respect to the stress oscillation amplitude \(\sigma_0\). The data are compatible with both exponential and power-law scalings with \(\sigma_0\), which hints at two possible interpretations in terms of delayed yielding in terms activated processes or of the Basquin law. Surprisingly, we find that the model parameters behave nonmonotonically as we change the oscillation frequency and/or the gel concentration.