An understanding of cosmic star formation requires a census of the cold molecular gas that fuels it, especially at the peak epoch of galaxy assembly. A detailed census of cold gas across cosmic time will be one of the major goals for the ngVLA. Here, we set the stage with the Karl G. Jansky VLA - CO Luminosity Density at high-z (COLDz) survey, the first spectral line deep field targeting CO(1-0) emission from galaxies at z~2-3 and CO(2-1) at z~5-7. These low-J CO lines are the most direct tracer of the cold molecular gas in galaxies. Therefore, COLDz provides the most robust constraints to date to the cosmic density of molecular gas at the peak epoch of cosmic star formation and beyond. COLDz covers a 60 times larger area than previous CO deep field studies. By targeting both a wide and a deep field, we provide the first significant constraints to the shape of the CO luminosity function at high redshift. Our line search for CO(1-0) uniformly selects starbursts and massive Main Sequence galaxies based on their cold molecular gas masses, yielding the first CO(1-0) blindly selected sample to date. We find a higher characteristic cold gas mass in galaxies at z~2-3 than predicted by semi-analytical models, as suggested by estimates based on dust emission, and higher-J CO lines. Our constraints to the cold gas content of galaxies over the z~2-7 range reproduce the cosmic star formation history for a typical gas depletion timescale of ~0.5 Gyr. Through CO line stacking, we find lower molecular gas mass fractions than expected in faint, Main Sequence galaxies. This legacy survey pushes the current VLA to its limits, demonstrating the potential of cm-wavelength, unbiased CO searches.