Strongly lensed active galactic nuclei (AGN) provide a unique opportunity to make progress in the study of the evolution of the correlation between the mass of supermassive black holes (M_BH) and their host galaxy luminosity (Lhost). We demonstrate the power of lensing by analysing two systems for which state-of-the-art lens modelling techniques have been applied to deep Hubble Space Telescope imaging data. We use (i) the reconstructed images to infer the total and bulge luminosity of the host and (ii) published broad-line spectroscopy to estimate M_BH using the so-called virial method. We then enlarge our sample with new calibration of previously published measurements to study the evolution of the correlation out to z ~ 4.5. Consistent with previous work, we find that without taking into account passive luminosity evolution, the data points lie on the local relation. Once the passive luminosity evolution is taken into account, we find that black holes in the more distant Universe reside in less luminous galaxies than today. Fitting this offset as M_BH/Lhost ∝ (1 + z)γ, and taking into account selection effects, we obtain γ = 0.6 ± 0.1 and 0.8 ± 0.1 for the case of M_BH-Lbulge and M_BH-Ltotal, respectively. To test for systematic uncertainties and selection effects we also consider a reduced sample that is homogeneous in data quality. We find consistent results but with considerably larger uncertainty due to the more limited sample size and redshift coverage (γ = 0.7 ± 0.4 and 0.2 ± 0.5 for M_BH-Lbulge and M_BH-Ltotal, respectively), highlighting the need to gather more high-quality data for high-redshift lensed quasar hosts. Our result is consistent with a scenario where the growth of the black hole predates that of the host galaxy.