Galaxies in the early Universe were more compact and contained more molecular gas than today. In this paper, we revisit the relation between these empirical findings, and we quantitatively predict the cosmic evolution of the surface densities of atomic (HI) and molecular (H2) hydrogen in regular galaxies. Our method uses a pressure-based model for the H2/HI ratio of the interstellar medium, applied to 3x10^7 virtual galaxies in the Millennium Simulation. We predict that, on average, the HI-surface density of these galaxies saturates at Sigma(HI)<10Msun/pc^2 at all redshifts (z), while H2-surface densities Sigma(H2) evolve dramatically as (1+z)^2.4. This scaling is dominated by a (1+z)^2 surface brightness scaling originating from the. (1+z)^-1 size scaling of galaxies at high z. Current measurements of Sigma(H2) at high z, derived from CO observations, tend to have even higher values, which can be quantitatively explained by a selection bias towards merging systems. However, despite the consistency between our high-z predictions and the sparse empirical data, we emphasize that the empirical data potentially suffer from serious selection biases and that the semi-analytic models remain in many regards uncertain. As a case study, we investigate the cosmic evolution of simulated galaxies, which resemble the Milky Way at z=0. We explicitly predict their HI and H2 distribution at z=1.5, corresponding to the CO-detected galaxy BzK-21000, and at z=3, corresponding to the primary science goal of the Atacama Large Millimeter/submillimeter Array (ALMA).