Fatigue is sort of a mix of plastic and elastic deformation. It can happen when a material is only being elastically stressed - but the mechanism of operation is still dislocation motion (like plastic deformation).

The dislocations that move in this case require much lower stress to move - ie. not all dislocations move at exactly the yield stress of the material (that's sort of an average). But in this case, dislocations move back and forth along the same path (the path of low resistance), and eventually form a slip band which can eventually lead to failure of the material.

This is referred to generally as high-cycle fatigue, ie. it takes a lt of cycles to cause failure, because the stresses are low, and SN (stress vs #cycles) curves are used to assess damage and predict time to failure (compared with a stress/strain curve used to predict failure from overstress).