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_kLambda$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.