Nanomaterials, i.e. materials with characteristic dimensions in the sub-micrometer range (<10^-6m), have become the focus of intense catalysis research after first reports on nanosized gold particles indicated that nano-scaled materials can show fundamentally different properties from their bulk (macroscopic) equivalent. Additionally, the extremely large surface-to-volume ratio of nanoparticles makes such materials highly interesting for catalytic applications. However, the thermal stability of particles decreases strongly with decreasing diameter, which currently restricts the application of metallic nanoparticles to low and moderate process temperatures (T<500°C). We are presenting the first successful approach to overcome this barrier by anchoring noble metal nanoparticles in a high-temperature stabilized alumina matrix. In this way, we were able to synthesize exceptionally active and sinter-resistant nano-composite materials, which combine the high reactivity of nanosized noble metal particles with the excellent high-temperature stability of structured aluminas. The materials show excellent activity and selectivity for catalytic partial oxidation of methane (CPOM) combined with unusual high-temperature stability up to temperatures in excess of 1000°C. Overall, these materials are highly promising catalysts for a broad range of high-temperature applications including catalytic combustion, ammoxidation, steam reforming, and water-gas shift.