Covariant density functional theory, which has so far been applied only within the framework of static and time-dependent mean-field theory, is extended to include particle-vibration coupling (PVC) in a consistent way. Starting from a conventional energy functional, we calculate the low-lying collective vibrations in the relativistic random phase approximation (RRPA) and construct an energy-dependent self-energy for the Dyson equation. The resulting Bethe-Salpeter equation in the particle-hole (p-h) channel is solved in the time blocking approximation (TBA). No additional parameters are used, and double counting is avoided by a proper subtraction method. The same energy functional, i.e., the same set of coupling constants, generates the Dirac-Hartree single-particle spectrum, the static part of the residual p-h interaction, and the particle-phonon coupling vertices. Therefore, a fully consistent description of nuclear excited states is developed. This method is applied for an investigation of damping phenomena in the spherical nuclei with closed shells Pb208 and Sn132. Since the phonon coupling terms enrich the RRPA spectrum with a multitude of p-h phonon components, a noticeable fragmentation of the giant resonances is found, which is in full agreement with experimental data and with results of the semiphenomenological nonrelativistic approach.