Density functional theory is generalized to incorporate electron-phonon coupling. A Kohn-Sham equation yielding the electronic density $n_U(mathbf{r})$, a conditional probability density depending parametrically on the phonon normal mode amplitudes $U={U_{mathbf{q}lambda}}$, is coupled to the nuclear Schrodinger equation of the exact factorization method. The phonon modes are defined from the harmonic expansion of the nuclear Schrodinger equation. A nonzero Berry curvature on nuclear configuration space affects the phonon modes, showing that the potential energy surface alone is generally not sufficient to define the phonons. An orbital-dependent functional approximation for the non-adiabatic exchange-correlation energy reproduces the leading-order nonadiabatic electron-phonon-induced band structure renormalization in the Frohlich model.