The aim of this chapter is to discuss analytical models for the prediction of fatigue crack nucleation and early growth. The preliminary stage frequently takes a significant portion of the total fatigue life. Moreover, even now, when the fail-safe and damage-tolerant concepts are widely spread in engineering applications, the formation of a macroscopic crack, e.g., a visible one, is sometimes considered as a kind of failure after which the structural component must be withdrawn out of operation. Putting apart structural safety considerations, one must state that the theory of crack nucleation and early growth enters, as an essential part, into the theory of fatigue. In particular, if a crack is born in a “natural” way, final conditions of the first stage become initial conditions for the stage of regular fatigue crack growth. We do not mention that some models used in the theory of fatigue crack nucleation intrinsically enter into the theory of fatigue crack propagation.