The electrochemical performance of aluminum-sulfur batteries is beset by poor stability and sluggish charge-storage properties. To address these issues, carbon allotropes have been used as electrode fillers, but successful outcomes remain inexplicably elusive. Here, a composite of sulfur and small diameter single-walled carbon nanotubes is synthesized and used as a cathode for reversible aluminum-sulfur batteries. The assembled electrode delivers a high capacity of 1024 mAh/g and effectively reduces the cell polarization by 37%. Moreover, the use of small-diameter SWCNT helps in lowering the electrolyte-to-sulfur ratio down to 17 μg/ml, an important step toward lean electrolyte conditions. Despite that, the capacity fade of the Al-S battery cannot be fully reversed. As we show, the consequence of the interaction between the electrolyte and S is the buildup of insoluble and poorly conductive discharge products, which inhibit charge diffusion and progressively deactivate the electrode, ultimately causing capacity decay. Overall, this works clarifies the carbon–sulfur–electrolyte interactions and their role in the underlying charge-storage mechanism of Al-S batteries.