Inorganic solids with low thermal conductivity are of great interest for thermoelectric applications. The formation of synthetic nanostructures by matrix encapsulation is one of the important strategies for thermal conductivity reduction through phonon scattering. Here, we report the reduction of lattice thermal conductivity near the theoretical minimum limit, κmin, in SnTe via spontaneous formation of nanodomains of the Sb-rich layered intergrowth SnmSb2nTe3n+m compounds, which are natural heterostructures. High-resolution transmission electron microscopy of Sn1-xSbxTe samples reveals the formation of endotaxial Sb rich nanoprecipitates (2-10 nm) along with super-structured intergrowth nanodomains (10-30 nm), which are the key features responsible for the significant reduction of lattice thermal conductivity in SnTe. This mechanism suggests a new avenue for the nanoscale engineering in SnTe to achieve low lattice thermal conductivities. Moreover, the presence of Sb improves the electronic transport properties by aliovalent cation doping which optimizes the hole concentration in SnTe. As a result, an enhanced thermoelectric figure of merit, zT, of ∼1 has been achieved for the composition of Sn0.85Sb0.15Te at 800 K. The high zT sample exhibits the Vickers microhardness value of ∼136 HV which is double that of pristine SnTe and is significantly higher than those of the present state-of-the-art thermoelectric materials.