This paper describes a new, high-performance, Pb-based nanocomposite anode material for lithium-ion batteries. A unique nanocomposite structure of Pb@PbO core-shell nanoparticles in a carbon matrix is obtained by using a simple high-energy ball milling method using the low-cost starting materials PbO and carbon black. Electrochemical performance tests show its excellent reversible capacity (≈600 mAh g−1) and cycle stability (92% retention at 100th cycle), which are one of the best values reported for Pb-based anodes in the literature. Synchrotron X-ray diffraction and absorption techniques revealed the detailed lithium storage mechanism that can be highlighted with the unexpectedly wide reversible Pb redox range (between Pb2+ and Pb4−) and the evolution of Zintl-type LiyPb structures during the electrochemical lithium reaction. The results provide new insights into the lithium storage mechanism of these Pb-based materials and their potential as low-cost, high-performance anodes.