Catalysts play an important role in many industrial processes, but their use in high-temperature applications-such as energy generation through natural gas combustion, steam reforming and the partial oxidation of hydrocarbons to produce feedstock chemicals--is problematic. The need for catalytic materials that remain stable and active over long periods at high operation temperatures, often in the presence of deactivating or even poisoning compounds, presents a challenge. For example, catalytic methane combustion, which generates power with reduced greenhouse-gas and nitrogen-oxide emissions, is limited by the availability of catalysts that are sufficiently active at low temperatures for start-up and are then able to sustain activity and mechanical integrity at flame temperatures as high as 1,300 degrees C. Here we use sol-gel processing in reverse microemulsions to produce discrete barium hexa-aluminate nanoparticles that display excellent methane combustion activity, owing to their high surface area, high thermal stability and the ultrahigh dispersion of cerium oxide on the their surfaces. Our synthesis method provides a general route to the production of a wide range of thermally stable nanostructured composite materials with large surface-to-volume ratios and an ultrahigh component dispersion that gives rise to synergistic chemical and electronic effects, thus paving the way to the development of catalysts suitable for high-temperature industrial applications.