In this paper, a Pd/reduced graphene oxide (Pd/RGO) catalyst was successfully synthesized by a chemical reduction method with hydrazine hydrate as a reducing agent. By controlling the amount of reducing agent, the Pd/RGO catalyst showed different surface Pd loadings and graphene interlayer spacings. The Pd/Fe@RGO catalyst was prepared by Pd supported on the Fe@RGO composite which was synthesized by a hydrothermal method. In the Pd/Fe@RGO catalyst, Pd⁰ species and Fe³⁺ species were the main active components. The addition of Fe species increased the interlayer spacing of graphene, the surface loading of Pd and the content of surface active oxygen. Thus, the Pd/Fe@RGO catalyst showed the highest catalytic activity for CO oxidation, and the T₁₀₀ value was 90 °C and the apparent activation energy was 86.37 kJ mol⁻¹. The superior catalyst at 50% conversion was stable for 510 min, and under moisture the catalyst was stable for only 300 min.