We present nanocrystalline PbS, which was prepared using a solvothermal method followed by spark plasma sintering, as a promising thermoelectric material. The effects of grains with different length scales on phonon scattering of PbS samples, and therefore on the thermal conductivity of these samples, were studied using transmission electron microscopy and theoretical calculations. We found that a high density of nanoscale grain boundaries dramatically lowered the thermal conductivity by effectively scattering long-wavelength phonons. The thermal conductivity at room temperature was reduced from 2.5 W m(-1) K-1 for ingot-PbS (grain size >200 mu m) to 2.3 W m(-1) K-1 for micro-PbS (grain size >0.4 mu m); remarkably, thermal conductivity was reduced to 0.85 W m(-1) K-1 for nano-PbS (grain size similar to 30 nm). Considering the full phonon spectrum of the material, a theoretical model based on a combination of first-principles calculations and semiempirical phonon scattering rates was proposed to explain this effective enhancement. The results show that the high density of nanoscale grains could cause effective phonon scattering of almost 61%. These findings shed light on developing high-performance thermoelectrics via nanograins at the intermediate temperature range.