Deep K -band imaging of the most luminous z \simeq 4 quasars currently offers the earliest possible view of the mass-dominant stellar populations of the host galaxies which house the first super-massive black holes in the Universe . This is because , until the advent of the James Webb Space Telescope , it is not possible to obtain the necessary deep , sub-arcsec resolution imaging at rest-frame wavelengths \lambda _ { rest } > 4000 Å at any higher redshift . We here present and analyse the deepest , high-quality K _ { S } -band images ever obtained of luminous quasars at z \simeq 4 , in an attempt to determine the basic properties of their host galaxies less than 1 Gyr after the first recorded appearance of black holes with M _ { bh } > 10 ^ { 9 } { M _ { \odot } } . To maximise the robustness of our results we have carefully selected two Sloan Digital Sky Survey quasars at z \simeq 4 . With absolute magnitudes M _ { i } < -28 , these quasars are representative of the most luminous quasars known at this epoch but they also , crucially , lie within 40 arcsec of comparably-bright foreground stars ( required for accurate point-spread-function definition ) , and have redshifts which ensure line-free K _ { S } -band imaging . The data were obtained in excellent seeing conditions ( < 0.4 -arcsec ) at the European Southern Observatory on the Very Large Telescope with integration times of \simeq 5.5 hours per source . Via carefully-controlled separation of host-galaxy and nuclear light , we estimate the luminosities and stellar masses of the host galaxies , and set constraints on their half-light radii . The apparent K _ { S } -band magnitudes of the quasar host galaxies are consistent with those of luminous radio galaxies at comparable redshifts , suggesting that these quasar hosts are also among the most massive galaxies in existence at this epoch . However , the quasar hosts are a factor \sim 5 smaller ( \langle r _ { 1 / 2 } \rangle = 1.8 { kpc } ) than the host galaxies of luminous low-redshift quasars . We estimate the stellar masses of the z \simeq 4 host galaxies to lie in the range 2 - 10 \times 10 ^ { 11 } { M _ { \odot } } , and use the CIV emission line in the Sloan optical spectra to estimate the masses of their central supermassive black holes . The results imply a black-hole : host-galaxy mass ratio M _ { bh } :M _ { gal } \simeq 0.01 - 0.05 . This is an order of magnitude higher than typically seen in the low-redshift Universe , and is consistent with existing evidence for a systematic growth in this mass ratio with increasing redshift ( i.e . M _ { bh } :M _ { gal } \propto ( 1 + z ) ^ { 1.4 - 2.0 } ) , at least for objects selected as powerful active galactic nuclei .