We predict the emission line luminosity functions (LFs) of the first 10 rotational transitions of CO in galaxies at redshift z=0 to z=10. This prediction relies on a recently presented simulation of the molecular cold gas content 3x10^7 evolving galaxies based on the Millennium Simulation. We combine this simulation with a model for the conversion between molecular mass and CO- line intensities, which incorporates the following mechanisms: (1) molecular gas is heated by the cosmic microwave background (CMB), starbursts (SBs), and active galactic nuclei (AGNs); (2) molecular clouds in dense or inclined galaxies can overlap; (3) compact gas can attain a smooth distribution in the densest part of disks; (4) CO luminosities scale with metallicity changes between galaxies; and (5) CO luminosities are always detected against the CMB. We analyze the relative importance of these effects and predict the cosmic evolution of the CO- LFs. The most notable conclusion is that the detection of regular galaxies (i. e., no AGN, no massive SB) at high z>7 in CO emission will be dramatically hindered by the weak contrast against the CMB, in contradiction to earlier claims that CMB heating will ease the detection of high-redshift CO. The full simulation of extragalactic CO lines and the predicted CO- LFs at any redshift can be accessed online (http://s-cubed.physics.ox.ac.uk/, go to "S3-SAX") and they should be useful for the modeling of CO-line surveys with future telescopes, such as the Atacama Large Millimeter/submillimeter Array or the Square Kilometer Array.