MnO2/CNT composite nanotubes with nanometer-sized flake-like MnO2 on carbon nanotubes' surfaces have been synthesized through an easy and efficient solution-based method. Similarly, Mn3O4/CNT composite nanotubes have also been synthesized by using the same method but different heat treatment process. The structures and compositions of the two types of composite nanotubes are characterized by using scanning electron microscopy, transmission electron microscopy, X-ray diffraction, and nitrogen adsorption-desorption isotherms. Electrochemical measurements indicate that the MnO2/CNT composites nanotubes exhibit significantly enhanced supercapacitance performance compared with the Mn3O4/CNT composite nanotubes, the as-synthesized MnO2 nanoparticles and commercial MnO2. The possibilities of the enhanced properties are illustrated on the basis of analysis of XRD and X-ray photoelectron spectroscopy measurements. Our results presented here can give clear evidence of the superiority of nanocrystalline MnO2 to nanocrystalline Mn3O4 toward the applications as electrode materials in electrochemical capacitors.