Thermostatically controlled loads (TCLs), such as refrigerators, air-conditioners and space heaters, offer significant potential for short-term modulation of their aggregate power consumption. This ability can be used in principle to provide frequency response services, but controlling a multitude of devices to provide a measured collective response has proven to be challenging. Many controller implementations struggle to manage simultaneously the short-term response and the long-term payback, whereas others rely on a real-time command-and-control infrastructure to resolve this issue. In this paper, we propose a novel approach to the control of TCLs that allows for accurate modulation of the aggregate power consumption of a large collection of appliances through stochastic control. By construction, the control scheme is well suited for decentralized implementation, and allows each appliance to enforce strict temperature limits. We also present a particular implementation that results in analytically tractable solutions both for the global response and for the device-level control actions. Computer simulations demonstrate the ability of the controller to modulate the power consumption of a population of heterogeneous appliances according to a reference power profile. Finally, envelope constraints are established for the collective demand response flexibility of a heterogeneous set of TCLs.