As an earth abundant material, PbS, has been paid extensive attention in the thermoelectric community. The high lattice thermal conductivity of PbS indicates there is room left to further improve thermoelectric performance of PbS. In this system we aimed to reduce the lattice thermal conductivity through nanostructuring grain sizes, which was processed by mechanical alloying followed by spark plasma sintering. We found that the lattice thermal conductivity can be reduced from ∼1.5 W m−1 K−1 at 723 K for PbS ingot to as low as ∼0.50 W m−1 K−1 for the PbS with nano-scale grain sizes, as a result, a ZT value of 0.80 at 723 K was achieved for 1.0% PbCl2 doped PbS with the second phases of Bi2S3 (Sb2S3, SrS, CaS). These results indicate that PbS is a robust alternative of PbTe and PbSe for medium temperature thermoelectric applications.