The objective of this study is to investigate the removal of methane (CH4), nitric oxide (NO), and carbon monoxide (CO) from simulated natural gas vehicle (NGV) exhaust over a palladium catalyst. The effects of changes in space velocity and natural gas sulfur (S) content were studied. The study suggests that the NGV has to be operated slightly rich of stoichiometry to achieve simultaneous removal of the three constituents. The CH4 conversion decreases with an increase in the space velocity. The CO and NO conversions remain unaffected over the space velocity range (10,000 hr-1 to 100,000 hr-1) investigated. The presence of sulfur dioxide in the exhaust lowers the CH4 conversion and increases the CO conversion in the rich region. The NO conversion remains unaffected. Studies were conducted over model catalysts to investigate the modes of CH4 removal from the simulated NGV exhaust. These investigations suggest that CH4 is oxidized by O2 in the lean region and by NO and O2 in the rich region.