The constitutive equation and the fatigue of anelastic media are described by using fractional order derivatives. The stress-strain relation, based on a generalization of the Kelvin-Voigt model, describes typical hysteresis cycles with the stress increasing as the number of cycles increases, a phenomenon known as cyclic hardening and observed in many materials such as, for instance, steel. Criteria are established to find the number of cycles which may cause fatigue for a strain with a given amplitude and frequency. They are based on the yield and fatigue stresses, on the melting temperature through the dissipated energy, and on the strain energy. In all the cases, it is seen that the number of cycles to failure is inversely proportional to the amplitude and to the frequency of the applied strain. Comparison to experimental data indicates that the model satisfies, at least qualitatively, the behavior of real materials under cyclic loading.