In this work, iron oxide (Fe3O4) nanoparticles were deposited on multi-walled carbon nanotubes (MWNTs) by a simple chemical coprecipitation method and Fe3O4-decorated MWNTs (Fe-MWNTs)/polypyrrole (PPy) nanocomposites (Fe-MWNTs/PPy) were prepared by oxidation polymerization. The effect of the PPy on the electrochemical properties of the Fe-MWNTs was investigated. The structures characteristics and surface properties of MWNTs, Fe-MWNTs, and Fe-MWNTs/PPy were characterized by X-ray diffraction and X-ray photoelectron spectroscopy, respectively. The electrochemical performances of MWNTs, Fe-MWNTs, and Fe-MWNTs/PPy were determined by cyclic voltammetry and galvanostatic charge/discharge characteristics in a 1.0 M sodium sulfite electrolyte. The results showed that the Fe-MWNTs/PPy electrode had typical pseudo-capacitive behavior and a specific capacitance significantly greater than that of the Fe-MWNT electrode, indicating an enhanced electrochemical performance of the Fe-MWNTs/PPy due to their high electrical properties.