Rare-earth-filled transition-metal pnictides having the skutterudite-type structure have been proposed for use as high-temperature thermoelectric materials to recover waste heat from vehicle exhaust, among other applications. A previous investigation by this research group of one of the most studied skutterudites, CeFe4Sb12, found that, when exposed to air, this material oxidized at temperatures that are considerably below the proposed maximum operating temperature. Here, by the combined use of TGA, powder XRD, and XANES, it has been found that the substitution of Ce3+ and Fe2+ for larger rare-earth and transition-metal elements (Eu2+ and Ru2+) results in a significantly higher oxidation temperature compared to that of CeFe4Sb12. This increase can be related to the increased orbital overlap provided by these larger atoms (Eu2+ and Ru2+ vs Ce3+ and Fe2+), enabling the development of stronger bonds. These results show how selective substitution of the constituent elements can significantly improve the thermal stability of materials.