  We analyze the Nelson-Barr approach to the Strong CP Problem. We derive the
necessary conditions in order to simultaneously reproduce the CKM phase and the
quark masses. Then we quantify the irreducible contributions to the QCD
topological angle, namely the corrections arising from loops of the colored
fermion mediators that characterize these models. Corrections analytic in the
couplings first arise at 3-loop order and are safely below current bounds;
non-analytic effects are 2-loop order and decouple as the mediators exceed a
few TeV. We discuss collider, electroweak, and flavor bounds and argue that
most of the parameter space above the TeV scale is still allowed in models with
down-type mediators, whereas other scenarios are more severely constrained.
With two or more families of mediators the dominant experimental bound is due
to the neutron electric dipole moment.
