We present observations with the IRAM Plateau de Bure Interferometer of three QSOs at z>5 aimed at detecting molecular gas in their host galaxies as traced by CO transitions. CO (5-4) is detected in SDSSJ033829.31+002156.3 at z=5.0267, placing it amongst the most distant sources detected in CO. The CO emission is unresolved with a beam size of ~1, implying that the molecular gas is contained within a compact region, less than ~3kpc in radius. We infer an upper limit on the dynamical mass of the CO emitting region of ~3x10^10 Msun/sin(i)^2. The comparison with the Black Hole mass inferred from near-IR data suggests that the BH-to-bulge mass ratio in this galaxy is significantly higher than in local galaxies. From the CO luminosity we infer a mass reservoir of molecular gas as high as M(H2)=2.4x10^10 Msun, implying that the molecular gas accounts for a significant fraction of the dynamical mass. When compared to the star formation rate derived from the far-IR luminosity, we infer a very short gas exhaustion timescale (~10^7 yrs), comparable to the dynamical timescale. CO is not detected in the other two QSOs (SDSSJ083643.85+005453.3 and SDSSJ163033.90+401209.6) and upper limits are given for their molecular gas content. When combined with CO observations of other type 1 AGNs, spanning a wide redshift range (0<z<6.4), we find that the host galaxy CO luminosity (hence molecular gas content) and the AGN optical luminosity (hence BH accretion rate) are correlated, but the relation is not linear: L(CO) ~ [lambda*L_lambda(4400A)]^0.72. Moreover, at high redshifts (and especially at z>5) the CO luminosity appears to saturate. We discuss the implications of these findings in terms of black hole-galaxy co-evolution.