We present the first results from a major Hubble Space Telescope program designed to investigate the cosmological evolution of quasar host galaxies from z~2 to the present day. Here we describe J and H-band NICMOS imaging of two quasar samples at redshifts of 0.9 and 1.9 respectively. Each sample contains equal numbers of radio-loud and radio-quiet quasars, selected to lie within the same narrow range of optical absolute magnitude (-24 > M_V > -25). Filter and target selection were designed to ensure that at each redshift the images sample the same part of the objects rest-frame spectrum, avoiding potential contamination by [OIII]lambda5007 and H-alpha emission lines. At z=1 the hosts of both radio-loud and radio-quiet quasars lie on the same Kormendy relation described by 3CR radio galaxies at comparable redshift. There is some evidence for a gap of ~1 mag between the host luminosities of RLQs and RQQs, a difference that cannot be due to emission-line contamination given the design of our study. However, within current uncertainties, simple passive stellar evolution is sufficient to link these galaxies with the elliptical hosts of low-redshift quasars of comparable nuclear output, implying that the hosts are virtually fully assembled by z=1. At z=2 the luminosity gap appears to have widened further to ~1.5 mag. Thus while the hosts of radio-loud quasars remain consistent with a formation epoch of z>3, allowing for passive evolution implies that the hosts of radio-quiet quasars are ~2-4 times less massive at z=2 than at low z.