The key physical processes driving galaxy formation and evolution are controlled by gas and, in particular, the process of star formation from cold, dense gas is not well understood since it depends upon the gas cooling ability, its dynamical state and complex feedback processes. Galaxies were observed to form stars much more rapidly in the past (~10-11 billion years ago), which may be due to larger gas reservoirs or more efficient star formation processes. While previous studies have identified large molecular gas reservoirs in a few pre-selected star-forming galaxies, an unbiased survey for molecular gas is necessary to provide robust statistical constraints to the gas content of galaxies at the peak epoch of cosmic star formation. Taking advantage of the improved frequency coverage, sensitivity and bandwidth of the upgraded Very Large Array we have carried out the first unbiased survey by performing a deep-field blind search for CO(1-0) line emission at z~2-3 and CO(2-1) line emission at z~5-7, targeting CO(1-0) which is the most commonly used tracer of the cold, dense molecular gas which fuels star formation. Having detected the first CO(1-0)-selected galaxies at high redshift, we have used their luminosity and abundance to provide robust statistical constraints to the CO luminosity function at z~2-3, finding conclusive evidence for a much higher gas mass content relative to galaxies in the local Universe. This finding suggested that evolution in the mechanisms of star formation may not be the dominant contribution to the high observed star formation rates, but rather large amounts of available cold gas. In order to explore how this finding may apply to even higher redshift, we have also achieved the first detection of CO emission in "normal" galaxies at z>5 (in the first billion years of cosmic time) together with far-infrared fine structure line tracers of the atomic and ionized gas using the sensitive Atacama Large(sub-)Millimeter Array. We found that early galaxies appear to be extremely gas rich, relative to their stellar content, and to display comparable star formation efficiency to typical lower redshift "normal" galaxies. However, the interstellar medium in a fraction of such galaxies also appears to be strongly affected by lower metallicity, affecting the phase structure of the interstellar medium, and the usefulness of CO as a tracer of molecular gas.