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.