Phosphorus-doped graphene layers have been formed on the surface of nanodiamond (ND) particles by hot pressing of a mixture of purified detonation ND powder and triphenylphosphine (TPP) at 1000 °C and 100 bar. X-ray photoelectron spectroscopy detected about 1.7 at.% of phosphorus in the product, most of which was in the oxidized form. The same treatment conditions of the ND powder without the addition of TPP resulted in the only partial covering of some ND particles by sp2-hybridized carbon layers. The tests in Na-ion half-cells found that the pure carbon sample can reversibly sustain 42 mAh g−1 at a current density of 0.1 A g−1. For the phosphorus-doped sample, this value increases up to 54 mAh g−1 due to mainly accumulation of sodium at various defects created in the graphitic layers as a result of phosphorus incorporation. Taking into account inertness of inner diamond cores, specific capacity values are 417 mAh g−1 for phosphorus-doped graphene layers and 587 mAh g−1 for non-doped ones.