Sodium-ion batteries (SIBs) have been pursued as a more cost-effective and more sustainable alternative to lithium-ion batteries (LIBs), but these advantages come at the expense of energy density. In this study, we demonstrate that the challenge of energy density for sodium chemistries can be overcome through an anode-free architecture enabled by the use of a nano-carbon nucleation layer formed on Al current collectors. The carbon nucleation layer lowers the overpotential for metal plating, supports uniform growth of sodium nuclei on the collector, and mitigates adverse effects of shorting or instability over extremely long cycling durations. Electrochemical studies demonstrate highly stable and efficient plating and stripping of sodium metal over a range of currents up to 4 mA/cm², sodium loading up to 12 mAh/cm², and with long-term durability exceeding 1,000 cycles at a current of 0.5 mA/cm². Building upon this anode-free architecture, we demonstrate a full cell using a pre-sodiated pyrite cathode to achieve energy densities of ~400 Wh/kg based on total mass of electrode materials and sodium, far surpassing recent reports on SIBs and even the theoretical maximum for LIB technology (387 Wh/kg for LiCoO₂/graphite cells) while still relying on naturally abundant raw materials and cost-effective aqueous processing.