A comprehensive analysis of electric dipole moment constraints on CP-violating phases in the MSSM.We analyze the constraints placed on individual, flavor diagonal CP-violating phases in the minimal supersymmetric extension of the Standard Model (MSSM) by current experimental bounds on the electric dipole moments (EDMs) of the neutron, Thallium, and Mercury atoms. We identify the four CP-violating phases that are individually highly constrained by current EDM bounds, and we explore how these phases and correlations among them are constrained by current EDM limits. We also analyze the prospective implications of the next generation of EDM experiments. We point out that all other CP-violating phases in the MSSM are not nearly as tightly constrained by limits on the size of EDMs. We emphasize that a rich set of phenomenological consequences is potentially associated with these generically large EDM-allowed phases, ranging from B physics, electroweak baryogenesis, and signals of CP-violation at the CERN Large Hadron Collider and at future linear colliders. Our numerical study takes into account the complete set of contributions from one- and two-loop EDMs of the electron and quarks, one- and two-loop Chromo-EDMs of quarks, the Weinberg 3-gluon operator, and dominant 4-fermion CP-odd operator contributions, including contributions which are both included and not included yet in the CPsuperH2.0 package. We also introduce an open-source numerical package, 2LEDM, which provides the complete set of two-loop electroweak diagrams contributing to the electric dipole moments of leptons and quarks.