In order to understand galaxy evolution through cosmic times it is critical to derive the properties of the molecular gas content of galaxies, i.e. the material out of which stars ultimately form. The last decade has seen rapid progress in this area, with the detection of massive molecular gas reservoirs at high redshifts in submillimeter-selected galaxies and quasars. In the latter case, molecular gas reservoirs have been quantified out to redshifts z>6, i.e. towards the end of cosmic reionization when the universe was less than one Gyr old. The recent discovery of molecular gas in more normal galaxies have extended these studies from the most extreme objects in the universe (SFR~1000M_sun/yr; quasars and submillimeter galaxies) to more 'normal' starforming systems at redshifts 1.5-2.5 (with SFR~100M_sun/yr). However, detecting the molecular gas reservoirs of high-redshift galaxies that only have moderate star formation rates (~<10 M_sun/yr, similar to the faint galaxies seen in the Hubble Ultra Deep Field) will likely have to await the completion of ALMA.