We report on the effects of cosmic rays (CRs) on the abundance of CO in $\rm H_2$ clouds under conditions typical for star-forming galaxies in the Universe. We discover that this most important molecule for tracing H$_2$ gas is very effectively destroyed in ISM environments with CR energy densities $\rm U_{CR}∼(50-10^{3})\times U_{CR,Gal}$, a range expected in numerous star-forming systems throughout the Universe. This density-dependent effect operates volumetrically rather than only on molecular cloud surfaces (i.e. unlike FUV radiation that also destroys CO), and is facilitated by: a) the direct destruction of CO by CRs, and b) a reaction channel activated by CR-produced He$^{+}$. The effect we uncover is strong enough to render Milky-Way type Giant Molecular Clouds (GMCs) very CO-poor (and thus CO-untraceable), even in ISM environments with rather modestly enhanced average CR energy densities of $\rm U_{CR}∼(10-50)\times\rm U_{CR,Gal}$. We conclude that the CR-induced destruction of CO in molecular clouds, unhindered by dust absorption, is perhaps the single most important factor controlling the CO-visibility of molecular gas in vigorously star-forming galaxies. We anticipate that a second order effect of this CO destruction mechanism will be to make the H$_2$ distribution in the gas-rich disks of such galaxies appear much clumpier in CO $J$=1--0, 2--1 line emission than it actually is. Finally we give an analytical approximation of the CO/H$_2$ abundance ratio as a function of gas density and CR energy density for use in galaxy-size or cosmological hydrodynamical simulations, and propose some key observational tests. ; Comment: Accepted for publication in ApJ, 29 pages