Electrochemical conversion reactions of metal oxides provide a new avenue to build high capacity anodes for sodium-ion batteries. However, the poor rate performance and cyclability of these conversion anodes remain a significant challenge for Na-ion battery applications because most of the conversion anodes suffer from sluggish kinetics and irreversible structural change during cycles. In this paper, we report an Fe2O3 single crystallites/reduced graphene oxide composite (Fe2O3/rGO), where the Fe2O3 single crystallites with a particle size of ∼300 nm were uniformly anchored on the rGO nanosheets, which provide a highly conductive framework to facilitate electron transport and a flexible matrix to buffer the volume change of the material during cycling. This Fe2O3/rGO composite anode shows a very high reversible capacity of 610 mAh g-1 at 50 mA g-1, a high Coulombic efficiency of 71% at the first cycle, and a strong cyclability with 82% capacity retention after 100 cycles, suggesting a potential feasibility for sodium-ion batteries. More significantly, the present work clearly illustrates that an electrochemical conversion anode can be made with high capacity utilization, strong rate capability, and stable cyclability through appropriately tailoring the lattice structure, particle size, and electronic conduction channels for a simple transition-metal oxide, thus offering abundant selections for development of low-cost and high-performance Na-storage electrodes.