  We present a solution to the strong CP problem, which relies on the
horizontal gauge symmetry and CP invariance in a full theory. Similar to other
Nelson-Barr type solutions, CP violation in both the strong and weak sectors in
the Standard model (SM) is attributed to the condensation of complex scalars
$\Phi$ in the model. The model is differentiated by others in that it explains
the hierarchy in quark-Higgs Yukawa coupling in the SM based on a series of
sequential breaking of the horizontal $SU(3)_{f}$ gauge symmetry. The
experimental constraint $\overline{\theta}\lesssim10^{-10}$ requires
$<\!\!\Phi\!\!>\,\lesssim\,10^{13}-10^{14}{\rm GeV}$ (vacuum expectation value
of complex scalars) and $\lambda\,\lesssim\,10^{-6}$ (scalar quartic coupling).
We show that this small coupling is natural in the sense of 'tHooft
naturalness. Compared to other models of Nelson-Barr type with CP breaking
scale $\Lambda_{CP}\lesssim10^{8}{\rm GeV}$, our model is more advantageous in
terms of consistency with the thermal leptogenesis.
