As a new type of high-performance material, gradient structural steel is widely used in engineering fields due to its unique microstructure and excellent mechanical properties. For the prevalent fatigue failure problem, the rate of change in the local grain size gradients along the structure (referred to as the gradient rate) is a key parameter in the design of gradient structures, which significantly affects the fatigue performance of gradient structural steel. In this study, a new method of 'Voronoi primary + secondary modeling' is adopted to successfully establish three typical high-strength steel models corresponding to the convex-, linear-, and concave-type gradient rates for gradient structures, focusing on the stress-strain response and crack propagation in structural steel with different gradient rates under cyclic loading. It was found that the concave gradient rate structural model is dominated by finer grains with larger volume fraction, which is conducive to hindering fatigue crack propagation and has the longest fatigue life, which is 16.16% longer than that of the linear gradient rate structure and 23.66% longer than that of the convex gradient rate structure. The simulation results in this study are consistent with the relevant experimental phenomena. Therefore, when regulating the gradient rate, priority should be given to increasing the volume fraction of fine grains and designing a gradient rate structure dominated by fine grains to improve the fatigue life of the material. This study presents a new strategy for designing engineering materials with better service performance.