In this study, we report on the formation behavior of homogeneous nanostructures and the thermal properties of quaternary system AgPbmSbTem+2 (silver- and antimony-doped PbTe, m = 18) that were synthesized via nanostructure crystallization engineering by controlling thermal processes. It is well known that with the addition of excess amounts of Ag and Sb into a PbTe system, nano-grained structures can be dispersed in the matrix of grains or segregated as clusters at the grain boundary of PbTe. Here, we observed the nanostructures with grain size ranging from 1 nm to 15 nm, which were synthesized under consecutive thermal procedures. They were examined by elaborated transmission electron microscopy. For thermal conductivity, the reduction rate was 20-30%, which mainly originated from decrease of the lattice thermal conductivity due to crystal phonon scattering (lattice vibrations) from formation of AgSbTe2 nanostructures in the PbTe grains. The lattice thermal conductivities of the entire system, with controlled AgSbTe2 nanostructures in PbTe matrix, are substantially lower than in other cases. Finally, the best thermal conductivity reduction rate is shown in AgPb18SbTe20 compound heat-treated at 923 K. As a result, these nano-grained PbTe materials could be expected to increase ZT from thermal conductivity reduction.