In engineering applications, plenty of components are subjected to variable-amplitude cyclic loading, resulting in fatigue damage, which is one of the main forms of structural damage. While the linear damage rule has long served as a fundamental approach, its limitations necessitate advancements for more accurate fatigue life predictions. Hence, this paper introduces a pioneering method termed nonlinear fatigue damage constrained topology optimization (NFDCTO). This method integrates several key components: the rainflow counting method to evaluate the non-proportional cyclic load levels, Basquin’s equation to describe the S-N curve, and Morrow’s plastic work interaction rule to calculate the nonlinear cumulative damage of the structure. Consequently, we establish a mathematical model for the NFDCTO method based on these components. The incorporation of penalized damage aggregation with the P-Normal function is used to address significant constraints and singularity challenges. Furthermore, by employing the adjoint method, we derive sensitivity equations for both the objective function and fatigue constraint function concerning the design variables. Subsequently, the superiority of the NFDCTO method over traditional linear fatigue damage method were verified applying 2D L-shaped beam and simply supported structures as examples. Concurrently, bridge structures were employed to investigate the effect of the sensitivity index of the material to the history of variable amplitude stresses on the optimization results. In addition, the influence of the fatigue penalty factor on the topology optimization results was assessed using a 2D cantilever beam. Finally, we verify the effectiveness and feasibility of the NFDCTO method in addressing fatigue optimization challenges for 3D structures utilizing two 3D examples.