We address the challenging issue of how CP violation is realized in higher dimensional gauge theories without higher dimensional elementary scalar fields. In such theories interactions are basically governed by a gauge principle and therefore to get CP violating phases is a nontrivial task. It is demonstrated that CP violation is achieved as the result of compactification of extra dimensions, which is incompatible with the 4-dimensional CP transformation. As a simple example we adopt a 6-dimensional U(1) model compactified on a 2-dimensional orbifold T2/Z4. We argue that the 4-dimensional CP transformation is related to the complex structure of the extra space and show how the Z4 orbifolding leads to CP violation. We confirm by explicit calculation of the interaction vertices that CP violating phases remain even after the rephasing of relevant fields. For completeness, we derive a rephasing invariant CP violating quantity, following a similar argument in the Kobayashi-Maskawa model which led to the Jarlskog parameter. As an example of a CP violating observable we briefly comment on the electric dipole moment of the electron. © 2010 The American Physical Society.