Crystal structure prediction methods and first-principles calculations have been used to explore low-energy structures of carbon monoxide (CO). Contrary to the standard wisdom, the most stable structure of CO at ambient pressure was found to be a polymeric structure of $Pna21$ symmetry rather than a molecular solid. This phase is formed from six-membered (four carbon + two oxygen) rings connected by C=C double bonds with two double-bonded oxygen atoms attached to each ring. Interestingly, the polymeric $Pna21$ phase of CO has a much higher energy density than trinitrotoluene (TNT). On compression to about 7 GPa, $Pna21$ is found to transform into another chainlike phase of $Cc$ symmetry which has similar ring units to $Pna21$. On compression to 12 GPa, it is energetically favorable for CO to polymerize into a purely single bonded $Cmca$ phase, which is stable over a wide pressure range and transforms into the previously known $Cmcm$ phase at around 100 GPa. Thermodynamic stability of these structures was verified using calculations with different density functionals, including hybrid and van der Waals corrected functionals.