We show that the $H_0$ tension can be resolved by making recombination
earlier, keeping the fit to cosmic microwave background (CMB) data almost
intact. We provide a suite of general necessary conditions to give a good fit
to CMB data while realizing a high value of $H_0$ suggested by local
measurements. As a concrete example for a successful scenario with early
recombination, we demonstrate that a model with time-varying $m_e$ can indeed
satisfy all the conditions. We further show that such a model can also be well
fitted to low-$z$ distance measurements of baryon acoustic oscillation (BAO)
and type-Ia supernovae (SNeIa) with a simple extension of the model.
Time-varying $m_e$ in the framework of $\Omega_k\Lambda$CDM is found to be a
sufficient and excellent example as a solution to the $H_0$ tension, yielding
$H_0=72.3_{-2.8} ^{+2.7}\,$km/sec/Mpc from the combination of CMB, BAO and
SNeIa data even without incorporating any direct local $H_0$ measurements.
Apart from the $H_0$ tension, this model is also favored from the viewpoint of
the CMB lensing anomaly.