The interaction of electrons with quantized phonons and photons underlies the ultrafast dynamics of systems ranging from molecules to solids, and it gives rise to a plethora of physical phenomena experimentally accessible using time-resolved techniques. Green’s function methods offer an invaluable interpretation tool since scattering mechanisms of growing complexity can be selectively incorporated in the theory. Currently, however, real-time Green’s function simulations are either prohibitively expensive due to the cubic scaling with the propagation time or do neglect the feedback of electrons on the bosons, thus violating energy conservation. We put forward a computationally efficient Green’s function scheme which overcomes both limitations. The numerical effort scales linearly with the propagation time while the simultaneous dressing of electrons and bosons guarantees the fulfillment of all fundamental conservation laws. We present a real-time study of the phonon-driven relaxation dynamics in an optically excited narrow band-gap insulator, highlighting the nonthermal behavior of the phononic degrees of freedom. Our formulation paves the way to first-principles simulations of electron-boson systems with unprecedented long propagation times.