I give an overview of recent experimental anomalies in B_s physics at the Tevatron, which may be hinting at
a new source of CP violation beyond the CKM mechanism in the Standard Model. I then investigate the connection between B_s mixing and Electric Dipole Moments within the framework of Minimal Flavor Violation.
A complete operator basis leading to preferential B_s mixing is constructed at the leading order in Yukawa insertions, and size of these operators required to explain Tevatron data is estimated. The impact of these operators and their close flavor relatives on EDMs is then discussed.