  We use the recently derived CP phase dependent analytic results for the
supersymmetric electro-weak 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
constrains the CP violating phase $\theta_{\mu}$ (the phase of the Higgs mixing
parameter $\mu$) and $\xi_2$ (the phase of the SU(2) gaugino mass $\tilde m_2$)
and as much as 60-90% of the region in the $\xi_2-\theta_{\mu}$ plane is
eliminated over a significant region of the MSSM parameter space by the BNL
constraint. The region of CP phases not excluded by the BNL experiment allows
for large phases and for a satisfaction of the EDM constraints via the
cancellation 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
experiment. The sparticle spectrum of these models lies within reach of the
planned accelerator experiments.
