Intensive studies have been carried out over the past decade to identify nanostructured thermoelectric materials that allow the efficient conversion of waste heat to electrical power. However, less attention has been paid to the stability of such materials under operating temperatures, typically 400 degrees C or higher. Conventionally nanostructured ceramics tend to undergo grain growth at high temperature, lowering the density of interfaces and raising the thermal conductivity, which is detrimental to device performance. Therefore it is preferable to identify materials with stable nanostructures, for example systems that undergo spontaneous phase separation. Here we investigate PbTe-GeTe alloys, in which spinodal decomposition occurs on initial cooling from above 580 degrees C, forming complex nanostructures consisting of Ge-rich and Pb-rich domains on different size scales. The resulting dense arrangement of interfaces, combined with mass fluctuation associated with Pb-Ge mixing, enhances phonon scattering and strongly reduces the thermal conductivity. Here we focus on the nominal composition Pb0.49Ge0.51Te and show that by tuning the synthesis procedure, we are able to control the pattern of compositional domains and the density of interfaces between them. This allows low lattice thermal conductivities to be maintained even after thermal cycling over the operating temperature range.