  We show that the Migdal-Eliashberg theory loses validity at a finite value
$\lambda_c$ of the electron-phonon coupling $\lambda$ regardless of the
underlying model Hamiltonian. The value of $\lambda_c$ is approximately between
3.0 and 3.7. The new phase that emerges at $\lambda>\lambda_c$ breaks the
lattice translational symmetry. Depending on the filling fraction and crystal
symmetry, it is an insulator or a Fermi liquid. Its characteristic feature is a
gap or a pronounced depression of the fermionic density of states near the
Fermi level. We establish the breakdown from within the Migdal-Eliashberg
theory by demonstrating that the normal state specific heat is negative for
$\lambda\ge 3.7$ and the quasiparticle lifetime vanishes in the strong coupling
limit. At fixed $\lambda>\lambda_c$, the transition to the new phase occurs at
a critical temperature higher than the superconducting transition temperature.
In addition, there is a first order phase transition between the new phase and
the superconducting state as we vary $\lambda$ across $\lambda_c$ at fixed
temperature. We put forward a new theory - lattice-fermionic theory of
superfluidity - that bridges the gap between the Migdal-Eliashberg approach and
the physics at stronger coupling. At small $\lambda$, our theory reduces to the
Migdal-Eliashberg theory and, past $\lambda_c$, it describes the new phase and
a range of other phenomena.
