We study theoretically the dynamical process of yielding in cyclically sheared amorphous materials, within a thermal elastoplastic model and the soft glassy rheology model. Within both models we find an initially slow accumulation, over many cycles after the inception of shear, of low levels of damage in the form strain heterogeneity across the sample. This slow fatigue then suddenly gives way to catastrophic yielding and material failure. Strong strain localization in the form of shear banding is key to the failure mechanism. We characterize in detail the dependence of the number of cycles before failure on the amplitude of imposed strain, the working temperature, and the degree to which the sample is annealed prior to shear. We discuss our finding with reference to existing experiments and particle simulations, and suggest new ones to test our predictions.