Density functional theory is generalized to incorporate electron-phonon coupling. A Kohn-Sham equation yielding the electronic density n_U(r), a conditional probability density depending parametrically on the phonon normal mode amplitudes U = {U_qλ}, 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 nonadiabatic exchange-correlation energy reproduces the leading-order nonadiabatic electron-phonon-induced band structure renormalization in the Frohlich model.