Strong-field laser excitation of solids can produce extremely nonlinear electronic and optical behaviour. As recently demonstrated, this includes the generation of high harmonics extending into the vacuum-ultraviolet and extreme-ultraviolet regions of the electromagnetic spectrum(1-8). High harmonic generation is shown to occur fundamentally differently in solids and in dilute atomic gases(1-6,9-13). How the microscopic mechanisms in the solid and the gas differ remains a topic of intense debate(1-11,14-18). Here we report a direct comparison of high harmonic generation in the solid and gas phases of argon and krypton. Owing to the weak van der Waals interaction, rare (noble)-gas solids are a near-ideal medium in which to study the role of high density and periodicity in the generation process. We find that the high harmonic generation spectra from the rare-gas solids exhibit multiple plateaus extending well beyond the atomic limit of the corresponding gas-phase harmonics measured under similar conditions. The appearance of multiple plateaus indicates strong interband couplings involving multiple single-particle bands. We also compare the dependence of the solid and gas harmonic yield on laser ellipticity and find that they are similar, suggesting the importance of electron-hole recollision in these solids. This implies that gas-phase methods such as polarization gating for attosecond pulse generation and orbital tomography could be realized in solids.