Catalytic performance of fresh and aged impregnated Pd/LaFeO3 and sol gel LaFe1−xPdxO3 Natural Gas Vehicle Three-Way Catalysts, in powder form and wash-coated on ceramic monolith, have been investigated. Aging at 980 °C in wet atmosphere has no detrimental effect on the structural properties with the preservation of the orthorhombic structure of the perovskite. On the other hand, a loss of specific surface area is accompanied with surface Pd enrichment on LaFe1−xPdxO3 through ex solution process. It was found that the mode of Pd incorporation and subsequent aging has a limited impact on the catalytic performance at low temperature for the NO/H2 reaction. On the other hand, sharp rate enhancement in NO and methane conversion occurs at high temperature related to change in the reaction pathway from methane combustion to reforming reactions producing more efficient reducing agents to reduce NO. Such behaviour has been explained by the coexistence of palladium stabilized at different oxidation state at the surface and inside the perovskite structure.