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)