We use the recently derived CP phase dependent analytic results for the sup
ersymmetric electroweak correction to g(mu)-2 to constrain the explicit CP
phases in softly broken supersymmetry using the new physics effect seen in
the g-2 Brookhaven measurement. It is shown that the BNL data strongly cons
train the CP violating phase theta (mu) (the phase of the Higgs mixing para
meter mu) and xi (2) [the phase of the SU(2) gaugino mass (m) over tilde (2
)] and as much as 60-90% of the region in the xi (2)-theta (mu) plane is el
iminated over a significant region of the MSSM parameter space by the BNL c
onstraint. The region of CP phases not excluded by the BNL experiment allow
s for large phases and for a satisfaction of the EDM constraints via the ca
ncellation mechanism. We find several models with large CP violation which
satisfy the EDM constraint via the cancellation mechanism and produce an a(
mu)(SUSY) consistent with the new physics signal seen by the Brookhaven exp
eriment. The sparticle spectrum of these models lies within reach of the pl
anned accelerator experiments.