An effect of Pt addition to improve the catalytic performance of Pd-modified Mn-hexaaluminate in the high-temperature oxidation of methane, especially in SO2 and water presence, has been studied. X-ray diffraction, high-resolution transmission electron microscopy, X-ray photoelectron spectroscopy, thermogravimetry and differential thermal analysis were used for the characterization of fresh and spent catalysts. Temperature-programmed reduction by hydrogen was employed to study the redox properties of the catalysts. Four high-temperature tests (at 670 °C) of the methane oxidation were applied to reveal the water and sulfur resistance of the catalysts: 1) dry methane-air feed; 2) wet methane-air feed containing 3 wt% of water vapor; 3) methane-air feed containing 1000 ppm of SO2; and 4) wet methane-air feed with 1000 ppm of SO2. The Pt-doped Pd-Mn-hexaaluminate catalyst with the atomic ratio of Pt/Pd < 0.3 has been shown to possess the highest catalytic activity in the oxidation of methane, high water and sulfur tolerance, and reducibility by hydrogen as compared to the monometallic Pd-Mn-hexaaluminate catalyst and the bimetallic catalysts with Pt/Pd > 0.5. From the formal kinetic data of the oxidation of methane on the fresh and deactivated catalysts, we assumed that deactivation of the catalysts is due to a decrease in the amount of catalytically active sites in the bimetallic 0.33Pt-0.67Pd(0.27)/MnLaAl11O19 catalyst and a change in the state of active component in the other catalysts. Their oxidation ability and redox behavior were shown to be associated with the highly dispersed PdO particles, a PdO layer (3–5 nm) covering the metal palladium particles as well as the Mn3+-enriched MnLaAl11O19. The improved water and sulfur resistance is found to correlate with the presence of particles of PtPd alloy, with its fraction not exceeding 50%.