Is CP a Gauge Symmetry?

We suggest here that CP is a discrete {\it gauge} symmetry, and is therefore not violated by quantum gravity. We show that four dimensional CP can arise as a discrete gauge symmetry in theories with dimensional compactification, if the original number of Minkowski dimensions equals $8k+1$, $8k+2$ or $8k+3$, and if there are certain restrictions on the gauge group; these conditions are met by superstrings. CP may then be broken spontaneously below $10^9$ GeV, explaining the observed CP violation in the kaon system without inducing a large EDMN. We discuss the phenomenology of such models, as well as the peculiar nature of cosmic ``CP strings'' which could be produced at the compactification scale. Such strings have the curious property that a particle carried around the string is turned into its CP conjugate. A single CP string renders four dimensional spacetime nonorientable.