Fatigue delamination is one of the most severe damage mode for laminated composites. A new cohesive zone model was adopted in this article for modeling fatigue delamination propagation in laminated composites, in which the G-N curve and Paris’ law were linked. This model was developed based on a new interpretation of fatigue delamination propagation: fatigue delamination propagation is a result of multiple onsets. A new fatigue cohesive constitutive law was constructed for describing fatigue damage accumulation in the inter-laminar interface of composites. All the parameters used in the constitutive law are with clear physical meaning and can be calibrated from the experimental G-N curve. Compared to the existing models for fatigue delamination in composites, the constitutive law developed in this model works independently in each element, without algorithms for getting the global crack information or tracking crack tip position. Considering the different deformation fields around the crack tip under mode II loading conditions, a new fatigue damage accumulation law was developed for mode II FDP, and the predicted Paris’ law for mode II was compared well with the experimental results.