AbstractCold molecular and atomic gas plays a central role in our understanding of early galaxy formation and evolution. It represents the component of the interstellar medium (ISM) that stars form out of, and its mass, distribution, excitation, and dynamics provide crucial insight into the physical processes that support the ongoing star formation and stellar mass buildup. We here present results that demonstrate the capability of the Atacama Large (sub-)Millimeter Array (ALMA) to detect the cold ISM and dust in “normal” galaxies at redshifts z=5–6. We also show detailed studies of the ISM in massive, dust-obscured starburst galaxies out to z>6 with ALMA, the Combined Array for Research in Millimeter-wave Astronomy (CARMA), the Plateau de Bure Interferometer (PdBI), and the Karl G. Jansky Very Large Array (VLA). These observations place some of the most direct constraints on the dust-obscured fraction of the star formation history of the universe at z>5 to date, showing that “typical” galaxies at these epochs have low dust content, but also that highly-enriched, dusty starbursts already exist within the first billion years after the Big Bang.