We consider constraints on CP-violating phases in the Constrained Minimal Supersymmetric Standard Model. We find that by combining cosmological limits on gaugino masses with experimental bounds on the neutron and electron electric dipole moments, we can constrain the phase of the Higgs mixing mass mu to he [theta(mu)] < pi/10, independent of choices of the other mass parameters in the model. The other CP-violating phase MA is essentially unconstrained.