Thanks to deep surveys in the rest-frame optical/UV and color-selection techniques, the star formation history of the universe has now been constrained through the era of galaxy assembly at z~1-3 and all the way out to the epoch of reionization. Yet despite such advances, little is currently known about the properties and evolution of the underlying molecular gas reservoirs ultimately fueling the star formation. I will present recent progress in detecting and mapping the star-forming interstellar medium in high-redshift galaxies, including a detailed case study of the gas-star formation connection in a z~4 submillimeter galaxy, as well as current efforts to expand the sample size beyond one. I will end with a discussion of future prospects for understanding the nature of high-redshift star formation and, consequently, how today’s galaxy population developed through cosmic time.