The electrochemical sodium-ion storage properties of graphene nanosheets (GNSs), carbon nanotubes (CNTs), mesocarbon microbeads (MCMBs), and activated carbon (AC) are investigated. An irreversible oxidation occurs for the AC electrode during desodiation, limiting its use in sodium-ion batteries. The MCMB electrode shows a negligible capacity (∼2 mA h g-1), since the graphitic structure has a low surface area and is thus not capable of storing a sufficient amount of Na+. In contrast, the CNT and GNS electrodes exhibit reversible capacities of 82 and 220 mA h g-1, respectively, at a charge-discharge rate of 30 mA g-1. The high electro-adsorption/desorption area, large number of Na+ entrance/exit sites, and a large d-spacing of GNSs contribute to their superior Na+ storage capacity. At a high rate of 5 A g-1, the GNS electrode still delivers a capacity of as high as 105 mA h g-1, indicating great high-power ability. The charge storage mechanism of the electrode is examined using an ex situ X-ray diffraction technique.