The relaxion mechanism provides a potentially elegant solution to the hierarchy problem without resorting to anthropic or other fine-tuning arguments. This mechanism introduces an axion-like field, dubbed the relaxion, whose expectation value determines the electroweak hierarchy as well as the QCD strong CP violating θ parameter. However, in the original model proposed by Graham, Kaplan and Rajendran (2015), the relaxion does not solve the strong CP problem, and in fact contributes to it, as the coupling of the relaxion to the Higgs field and the introduction of a linear potential for the relaxion produces large strong CP violation. We resolve this tension by considering inflation with a Hubble scale which is above the QCD scale but below the weak scale, and estimating the Hubble temperature dependence of the axion mass. The relaxion potential is thus very different during inflation than it is today. We find that provided the inflationary Hubble scale is between the weak scale and about 3 GeV, the relaxion resolves the hierarchy, strong CP, and dark matter problems in a way that is technically natural.