Nelson-Barr models, which assume that CP is a spontaneously broken symmetry of nature, are a well-known solution to the strong CP problem with no new light degrees of freedom. Nevertheless, the spontaneous breaking of CP can have dramatic implications in cosmology. It was recently shown that domain walls which form from this spontaneous breaking are exactly stable, and therefore must be inflated away. Combined with the "Nelson-Barr quality problem", which sets an upper bound on the breaking scale to avoid the effects of dangerous irrelevant operators, this puts an upper bound on the scale of inflation and the subsequent reheating temperature. In this talk, I will briefly review the Nelson-Barr solution to the strong CP problem, its quality problem, and demonstrate that minimal Nelson-Barr models are in tension with simple models of inflation and thermal leptogenesis. I will also show one possibility for ameliorating this tension by introducing a new, chiral symmetry which forbids the most dangerous dimension-5 operators.