CP violation beyond the observed phase of the CKM matrix in the Standard Model (SM) is a necessary ingredient for Baryogenesis. If the beyond-the-SM CP violation is accompanied also by new sources of flavour violation constraints from low energy flavor observable can be severe. When, however, CP violation is not intertwined with dangerous FCNCs, measurements of electric dipole moments (EDMs) of the electron and nuclei may provide some of the best chances of detecting CP violation beyond the SM. In this talk, I discuss the complementarity of LHC searches and EDM constraints in probing anomalous (CP-violating) Higgs Yukawas. Given the expected progress in both the experimental and lattice-QCD side I will discuss the corresponding residual theory uncertainties, and stress the importance of probing multiple EDMs. Another intriguing question related to CP, is why it is a good symmetry of the strong interactions. In the axion solutions to the strong CP problems, this is explained via the dynamics of the goldstone boson of the PQ symmetry (the axion). In many axion models, SM fermions carry non-universal PQ charges, which induce flavor violating couplings of the axion. I discuss the corresponding constraints and present a new method to probe such couplings at LHCb.