Fatigue design of engineering structures is typically based on lifetime calculation using a cumulative damage law. The linear damage rule by Miner is the universal standard for fatigue design even though numerous experimental studies have shown its deficiencies and possible non-conservative outcomes. In an effort to overcome these deficiencies, many nonlinear cumulative damage models and life prediction models have been developed since; however, none of them have found wide acceptance. This review article aims to provide a comprehensive overview of the state-of-the art in cumulative damage and lifetime prediction models for endurance based high-cycle fatigue design of metal structures.