It is widely believed that in an adiabatic limit a Fermi liquid state of an electron-phonon system described by Migdal-Eliashberg theory remains stable before a dressed phonon softens or superconductivity sets in. Using Holstein model as a prototypical example and variational/analytic considerations we demonstrate that in a wide range of fillings both in 3D and 2D, a polaronic state emerges before phonon softening; at small filling in 3D this happens already at weak coupling. We show that a polaronic state emerges, upon increasing coupling, via an intermediate pseudogap-type mixed state, in which some fermions preserve Fermi liquid behavior, yet Luttinger theorem is broken. At even larger couplings the density of states gradually approaches its form in the atomic limit (a discrete set of delta-functions).