Electric dipole moments (EDMs) of elementary particles and atoms probe violations of T and P symmetries and consequently of CP if CPT is an exact symmetry. We point out that EDMs can also serve as sensitive probes of CPT-odd but CP-even interactions. In a class of theories where the breaking of CPT is introduced via the breaking of Lorentz invariance, we identify the leading dimension five operators that induce non-zero EDMs. We find that the EDMs of neutrons, and heavy diamagnetic atoms provide best sensitivity to the T, P, CPT-odd interactions, allowing to probe energy scales as high as 1012 GeV. We also point out that additional tests of Lorentz invariance are required in order to distinguish between CP-odd and CPT-odd effects, should non-zero EDMs be found.