Phosphorus has received recent attention in the context of high-capacity and high-rate anodes for lithium and sodium-ion batteries. Here, we present a first principles structure prediction study combined with NMR calculations which gives us insights into its lithiation/sodiation process. We report a variety of new phases found by the ab initio random structure searching (AIRSS) and the atomic species swapping methods. Of particular interest, a stable Na5P4– C2/m structure and locally stable structures found less than 10 meV/f.u. from the convex hull, such as Li4P3–P212121, NaP5–Pnma and Na4P3–Cmcm. The mechanical stability of Na5P4– C2/m and Li4P3–P212121 has been studied by first principles phonon calculations. We have calculated average voltages which suggests that black phosphorus (BP) can be considered as a safe anode in lithium-ion batteries due to its high lithium insertion voltage, 1.5 V; moreover, BP exhibits a relatively low theoretical volume expansion compared with other intercalation anodes, 216% (∆V/V). We identify that specific ranges in the calculated shielding can be associated with specific ionic arrangements, results which play an important role in the interpretation of NMR spectroscopy experiments. Since the lithium-phosphides are found to be insulating even at high lithium concentrations we show that Li-P-doped phases with aluminium have electronic states at the Fermi level suggesting that using aluminium as a dopant can improve the electrochemical performance of P anodes.