In this paper, a reliable progressive fatigue damage model (PFDM) for predicting the fatigue life of composite laminates is proposed by combining the normalized fatigue life model, nonlinear residual degradation models and fatigue-improved Puck criterion. To balance the accuracy of life predictions and computational efficiency, an adaptive cyclic jump algorithm is developed and implemented within the PFDM. The sensitivity of life prediction to cyclic jump parameter has been greatly reduced by correlating the cyclic jump with the increment time and viscous coefficient. Therefore, the cyclic jump parameter can be arbitrarily selected within a relatively large range to obtain convergent results. When incorporating the adaptive cyclic jump algorithm, there is no need to define a standard for determining the material failure in numerical calculations, which effectively eliminates an artificially induced uncertainty in life predictions. Two sets of experiments are conducted to validate the proposed PFDM. The numerical predictions including static failure strength and fatigue life correlate reasonably well with the available experimental data.