We report high thermoelectric performance in nanostructured p-type PbS, a material consisting of highly earth abundant and inexpensive elements. The high level of Na doping switched intrinsic n-type PbS to p-type and substantially raised the power factor maximum for pure PbS to ~9.0 μW cm(-1) K(-2) at >723 K using 2.5 at. % Na as the hole dopant. Contrary to that of PbTe, no enhancement in the Hall coefficient occurs at high temperature for heavily doped p-type PbS, indicating a single band model and no heavy hole band. We also report that the lattice thermal conductivity of PbS can be greatly reduced by adding SrS or CaS, which form a combination of a nanostructured/solid solution material as determined by transmission electron microscopy. We find that both nanoscale precipitates and point defects play an important role in reducing the lattice thermal conductivity, but the contribution from nanoscale precipitates of SrS is greater than that of CaS, whereas the contribution from point defects in the case of CaS is greater than that of SrS. Theoretical calculations of the lattice thermal conductivity based on the modified Callaway model reveal that both nanostructures and point defects (solid solution) effectively scatter phonons in this system. The lattice thermal conductivity at 723 K can be reduced by ~50% by introducing up to 4.0 at. % of either SrS or CaS. As a consequence, ZT values as high as 1.22 and 1.12 at 923 K can be achieved for nominal Pb(0.975)Na(0.025)S with 3.0 at. % SrS and CaS, respectively. No deterioration was observed after a 15 d annealing treatment of the samples, indicating the excellent thermal stability for these high performance thermoelectrics. The promising thermoelectric properties of nanostructured PbS point to a robust low cost alternative to other high performance thermoelectric materials.