We report on the response of a yield stress material, namely, a colloidal gel made of attractive carbon black particles, submitted to large amplitude oscillatory shear stress (LAOStress) in a Couette geometry. At a constant stress amplitude well below its apparent yield stress, the gel displays fatigue and progressively turns from an elastic solid to a viscous fluid. The time-resolved analysis of the strain response, of the Fourier components, and of Lissajous plots allows one to define two different timescales tau(w) < tau(f) associated with the yielding and fluidization of the gel. Coupling rheology to ultrasonic imaging further leads to a local picture of the LAOStress response in which the gel first fails at the walls at tau(w) and then undergoes a slow heterogeneous fluidization involving solid-fluid coexistence until the whole sample is fluid at tau(f). Spatial heterogeneities are observed in both the gradient and vorticity directions and suggest a fragmentation of the initially solidlike gel into macroscopic domains eroded by the surrounding fluidized suspension. (C) 2014 The Society of Rheology.