Thermoelectrics interconvert heat to electricity and are of great interest in waste heat recovery, solid-state cooling and so on. The efficiency of thermoelectric materials depends directly on the average ZT (dimensionless figure of merit) over a certain temperature range, which historically has been challenging to increase. Here we report that 2.5% K-doped PbTe0.7S0.3 achieves a ZT of >2 for a very wide temperature range from 673 to 923 K and has a record high average ZT of 1.56 (corresponding to a theoretical energy conversion efficiency of ~20.7% at the temperature gradient from 300 to 900 K). The PbTe0.7S0.3 composition shows spinodal decomposition with large PbTe-rich and PbS-rich regions where each region exhibits dissimilar types of nanostructures. Such high average ZT is obtained by synergistically optimized electrical- and thermal-transport properties via carrier concentration tuning, band structure engineering and hierarchical architecturing, and highlights a realistic prospect of wide applications of thermoelectrics.