We consider the effect of CP violating phases in the MSSM on the relic density of the lightest supersymmetric particle (LSP). In particular, we find that the upper limits on the LSP mass are relaxed when phases in the MSSM are allowed to take non-zero values when the LSP is predominantly a gaugino (bino). Previous limits of mB ≲ 250 GeV for Ωh2 < 0.25 can be relaxed to mB ≲ 650 GeV. We also consider the additional constraints imposed by the neutron and electron electric dipole moments induced by these phases. Though there is some restriction on the phases, the bino mass may still be as large as ∼ 350 GeV and certain phases can be arbitrarily large.