We analyze constraints on supersymmetric theories imposed by the experimental bounds on the electron, neutron, and mercury electric dipole moments. We conclude that only the scenarios with approximate CP-symmetry or flavour-off-diagonal CP violation remain attractive after the addition of the mercury EDM constraint. Two specific models with these features are presented.