Rechargeable aluminum-metal batteries promise low cost and and high energy density, as aluminum metal has a theoretical volumetric capacity (8040 mAh/cm³) that is almost four times higher than lithium metal. Various cathode materials (e.g., V₂O₅ nanowires, Mo₆S₈, etc.) have been shown to reversibly intercalate aluminum ions, but obstacles such as low working voltages, self-discharge, and low mobilities of intercalated ions are typically observed. Novel graphite-based cathodes have recently been developed that exhibit high cyclability, good discharge voltage plateaus (ca. 2 V), and high rate performances when paired with aluminum anodes and a AlCl₃/[EMIm]Cl ionic liquid electrolyte. However, the relationship between the local carbon structure and electrochemical properties of the electrodes is not well understood. Here, we report novel graphene-based electrodes that exhibit high specific capacity (e.g., >100 mAh/g at a current density of 66 mA/g) and discuss how the structural features of various carbon-based cathodes (e.g. synthetic, natural, and exfoliated graphite compounds) correlate with the electrode’s electrochemical properties and cell performance. Galvanostatic cycling and cyclic voltammetry analyses were performed to track electrode performance at various current densities, cycle numbers, and states-of-charge. Ex situ solid-state magic-angle-spinning (MAS) NMR spectroscopy was used to probe the local environments, relative populations, and dynamics of chloroaluminate and solvent species within the carbon electrodes, while X-ray diffraction and electron microscopy were conducted to analyze how the intercalation processes affected their local structures, periodic layering, and morphologies. These studies seek to unveil correlations of local carbon structure with electrochemical performance to aid the development of rechargeable aluminum-carbon batteries.