We use the results from the ALMA large program ASPECS, the spectroscopic survey in the Hubble Ultra Deep Field (HUDF), to constrain CO luminosity functions of galaxies and the resulting redshift evolution of {rho}(H_2_). The broad frequency range covered enables us to identify CO emission lines of different rotational transitions in the HUDF at z>1. We find strong evidence that the CO luminosity function evolves with redshift, with the knee of the CO luminosity function decreasing in luminosity by an order of magnitude from ~2 to the local universe. Based on Schechter fits, we estimate that our observations recover the majority (up to ~90%, depending on the assumptions on the faint end) of the total cosmic CO luminosity at z=1.0-3.1. After correcting for CO excitation, and adopting a Galactic CO-to-H_2_ conversion factor, we constrain the evolution of the cosmic molecular gas density {rho}(H_2_): this cosmic gas density peaks at z~1.5 and drops by a factor of 6.5_-1.4_^+1.8^ to the value measured locally. The observed evolution in {rho}(H_2_), therefore, closely matches the evolution of the cosmic star formation rate density {rho}SFR. We verify the robustness of our result with respect to assumptions on source inclusion and/or CO excitation. As the cosmic star formation history can be expressed as the product of the star formation efficiency and the cosmic density of molecular gas, the similar evolution of {rho}(H_2_) and {rho}SFR leaves only little room for a significant evolution of the average star formation efficiency in galaxies since z~3 (85% of cosmic history).