A multivalent aluminum metal anode (AMA) can deliver high specific/volumetric capacities of 2,980 mA h g−1/8,040 mA h cm−3 in an ionic liquid-AlCl3 electrolyte system. However, the large concentration overpotential of AMA induced by its distinctive anion-mediated aluminum metal redox mechanism causes poor rate capabilities and insufficient round-trip efficiencies, limiting its application in rechargeable aluminum batteries (RABs). In this paper, we report a novel strategy of using a carbonaceous catalytic host electrode for high-performance AMA. The targeted carbon electrode should have a high active surface area, strong interaction with ionic charge carriers, well-developed electronic pathways, and macroporous internal structures to accommodate incessantly deposited metals. In this regard, a 3D-structured carbon nanotube forest (CNT-F) was fabricated from waste polyolefins by a simple pyrolysis process as an optimal candidate for the catalytic host electrode. The waste-induced pyrolytic CNT-Fs (WP-CNT-F) had large open surface areas covered with multitudinous intrinsic carbon defects, on which uniform aluminum reduction reactions occurred concurrently, leading to significantly lower concentration overpotentials. In addition, the WP-CNT-Fs exhibited high coulombic efficiencies of 99.4–99.8% over a wide range of current densities (0.5–4.0 mA cm−2) and great cycling stabilities over 1,000 cycles. The superior electrochemical performances of the WP-CNT-F-based AMA were demonstrated in the RAB full cells with a commercial graphite cathode, affording a high specific energy and a high power density of ∼ 132.2 W h kgelectrode-1 and 10,230 W kgelectrode-1, respectively, along with outstanding cycling stabilities over 2,500 cycles.