The Pd-Zr- and Pd-Rh zeolite catalysts were synthesized and characterized by an x-ray powder diffractometer, a scanning electron microscope, an x-ray fluorescence instrument, a microbalance and nitrogen adsorption. The synthesized catalysts were tested for the removal of emissions from natural gas driven vehicles. The catalysts were hydrothermally aged and tested under similar reaction conditions as those of the fresh catalysts to study the mechanism of catalyst deactivation and its stabilization by zirconium and rhodium. The microbalance was used to study the redox behaviour of the catalysts. The modifications of Pd-Beta zeolite by Zr and Rh were found to stabilize the PdO species in the Beta zeolite structure. The Pd-Zr- and Pd-Rh-Beta zeolite catalysts exhibited high catalytic activity in the removal of NO, CO and unburned methane from natural gas driven vehicles.