  We combine results from deep ALMA observations of massive
($M_*>10^{10}\;M_{\odot}$) galaxies at different redshifts to show that the
column density of their inter stellar medium (ISM) rapidly increases towards
early cosmic epochs. Our analysis includes objects from the ASPECS and ALPINE
large programs, as well as individual observations of $z\sim 6$ QSO hosts. When
accounting for non-detections and correcting for selection effects, we find
that the median surface density of the ISM of the massive galaxy population
evolves as $\sim(1+z)^{3.3}$. This means that the ISM column density towards
the nucleus of a $z>3$ galaxy is typically $>100$ times larger than locally,
and it may reach values as high as Compton-thick at $z\gtrsim6$. Remarkably,
the median ISM column density is of the same order of what is measured from
X-ray observations of large AGN samples already at $z\gtrsim2$.
  We develop a simple analytic model for the spatial distribution of ISM clouds
within galaxies, and estimate the total covering factor towards active nuclei
when obscuration by ISM clouds on the host scale is added to that of pc-scale
circumnuclear material (the so-called 'torus'). The model includes clouds with
a distribution of sizes, masses, and surface densities, and also allows for an
evolution of the characteristic cloud surface density with redshift,
$\Sigma_{c,*}\propto(1+z)^\gamma$. We show that, for $\gamma=2$, such a model
successfully reproduces the increase of the obscured AGN fraction with redshift
that is commonly observed in deep X-ray surveys, both when different absorption
thresholds and AGN luminosities are considered.
  Our results suggest that 80-90\% of supermassive black holes in the early
Universe ($z>6-8$) are hidden to our view, primarily by the ISM in their hosts.
[abridged]
