Materials with very low thermal conductivity are of high interest for both thermoelectric and optical phase-change applications. Synthetic nanostructuring is most promising to suppress thermal conductivity by scattering phonons, but challenges remain in producing bulk samples. We show that in crystalline AgSbTe$_2$, a spontaneously-forming nanostructure leads to a suppression of thermal conductivity to a glass-like level. Our mapping of the phonon mean-free-paths provides a novel bottom-up microscopic account of thermal conductivity, and also reveals intrinsic anisotropies associated with the nanostructure. Ground-state degeneracy in AgSbTe$_2$ leads to the natural formation of nanoscale domains with different orderings on the cation sublattice, and correlated atomic displacements, which efficiently scatter phonons. This mechanism is general and points to a new avenue in nano-scale engineering of materials, to achieve low thermal conductivities for efficient thermoelectric converters and phase-change memory devices.