Nowadays, composite materials are used in different applications. Some of these applications involve components subject to cyclic loading. Fatigue is the dominant failure mechanism for structures under this type of loading. Hence, proper prediction of fatigue life is essential for safe design and operation of structures, maintenance, repair and replacement of components. Many of the existing models in this field have not assessed the degradation of material properties such as stiffness and strength during fatigue damage. In this paper, a stiffness-based model is initially evaluated for fatigue damage analysis of composite structures. The model is validated with two sets of experimental data. A residual strength model is coupled to the choice model and a modified model is developed. Then, residual fatigue life of fiber reinforced polymeric composites is predicted for three sets of experimental data under two-stage loading. The results demonstrate that the proposed model has an improvement on accuracy in the estimation of residual fatigue lives. For better evaluation of the developed model, experimental results and some existing models are compared with the present study predictions. It is concluded that in most cases, the predicted values by the proposed model is closer to experimental values in comparison with other models.