From an environmental perspective, lead-free SnTe would be preferable for solid-state waste heat recovery if its thermoelectric figure-of-merit could be brought close to that of the lead-containing chalcogenides. We studied the thermoelectric properties of nanostructured SnTe with different dopants, and found indium-doped SnTe showed extraordinarily large Seebeck coefficients that cannot be explained properly by the conventional two-valence band model. We attributed this enhancement of Seebeck coefficients to resonant levels created by the indium impurities inside the valence band, supported by the first-principles simulations. This, together with the lower thermal conductivity resulting from the decreased grain size by ball milling and hot pressing, improved both the peak and average nondimensional figure-of-merit (ZT) significantly. A peak ZT of ~1.1 was obtained in 0.25 atom % In-doped SnTe at about 873 K.