The main challenges to implement sustainable energy storage technologies are the utilization of earth-abundant recyclable materials, low costs, safe cell reactions and high performance, all in a single system. Aluminum batteries seem to cover these requirements. However, their practical performance is still not comparable with the state of the art high performance batteries. A key aspect to further development could be the combination of aluminum with charge storage materials like conductive polymers in non-aqueous electrolytes taking advantage of the properties of each material. This review presents the approaches and perspectives for rechargeable aluminum-based batteries as sustainable high-performance energy storage devices.