Sr₂(MgMo)₂O_6−δ and materials of nominal compositions with increased and decreased Mo content were synthesized and their stability and catalytic activity towards CH₄ oxidation characterized under solid oxide fuel cell (SOFC) anode conditions. Sr₂(MgMo)₂O_6−δ was synthesized as a double perovskite. Materials with increased Mo content formed a mixture of the double perovskite Sr₂MgMoO_6−δ and the single perovskite SrMoO₃, after synthesis in H₂, with the amount of SrMoO₃ increasing with increasing Mo content. SrMoO₃ is unstable in air and slowly oxidized to the scheelite-structured impurity SrMoO₄. All compositions decomposed to Mo, MgO and SrO in dry 20% CH₄/N₂ at temperatures ≥ 850 °C. CH₄ reaction rates were catalytically limited with measured rates significantly lower than for La_0.75Sr_0.25Cr_0.5Mn_0.5O_3-δ. Rates increased by 1–2 orders of magnitude when 2 wt-% of Pt was added to the surface.