Understanding the relationship between the formation and evolution of galaxies and their central super massive black holes (SMBH) is one of the main topics in extragalactic astrophysics. Links and feedback may reciprocally affect both black hole and galaxy growth. Observations of the CO line at redshifts of 2-4 are crucial to investigate the gas mass, star formation activity and accretion onto SMBHs, as well as the effect of AGN feedback. Potential correlations between AGN and host galaxy properties can be highlighted by observing extreme objects. Despite their luminosity, hyper-luminous QSOs at z=2-4 are still little studied at mm wavelengths. We targeted CO(3-2) in ULAS J1539+0557, an hyper-luminos QSO (Lbol> 10^48 erg/s) at z=2.658, selected through its unusual red colors in the UKIDSS Large Area Survey (ULAS). We find a molecular gas mass of 4.1+-0.8 10^10 Msun, and a gas fraction of 0.4-0.1, depending mostly on the assumed source inclination. We also find a robust lower limit to the star-formation rate (SFR=250-1600 Msun/yr) and star-formation efficiency (SFE=25-350 Lsun/(K km s-1 pc2) by comparing the observed optical-near-infrared spectral energy distribution with AGN and galaxy templates. The black hole gas consumption timescale, M(H_2)/dM(accretion)/dt, is ~160 Myr, similar or higher than the gas consumption timescale. The gas content and the star formation efficiency are similar to those of other high-luminosity, highly obscured QSOs, and at the lower end of the star-formation efficiency of unobscured QSOs, in line with predictions from AGN-galaxy co-evolutionary scenarios. Further measurements of the (sub)-mm continuum in this and similar sources are mandatory to obtain a robust observational picture of the AGN evolutionary sequence.