The electronic structures of M-doped SnTe (M = Mg, Mn, Cd, and Hg) are investigated by using first-principles calculations including spin-orbit coupling. It is found that Sn vacancy plays an important role in the band engineering of SnTe, showing a different property from its related compound PbTe. The enlarged band gap and reduced energy separation between two valence bands are in good agreement with experimental measurements. Both of the two band modifications lead to the increase of Seebeck coefficients, which is explicitly confirmed by the followed Boltzmann transport calculations. The calculated Seebeck coefficients for Mn-doped SnTe agree well with the experimental data in a broad range of carrier concentration. Owing to the improved Seebeck coefficients, Mn- and Cd-doped SnTe exhibit promising thermoelectric properties with ZT = 1.32 and 1.65 at around 800 K, respectively.