The fundamentals of our understanding of fatigue crack propagation were formed more than 60 years ago by Paul C. Paris. Since then, the run toward new metallic materials and alloys with ever finer-grained microstructures has had a large impact on research. Along with enormous variation of the microstructural length scales (i.e., grain size), the essential parameters for the description of fatigue crack growth, such as the crack propagation rate and plastic zone size, also exhibit an immense change from the subnanometer to the micrometer regime. These enormous variations in the fatigue crack growth behavior’s controlling parameters motivate this contribution. This article presents an overview of the effect of grain size, from the millimeter to the nanometer grain-size regime, on fatigue crack propagation of mainly ductile metals and alloys with an attempt to summarize the most important findings and underlying physical phenomena, including with respect to selected materials such as pure iron, nickel, and austenitic and pearlitic steel.