Na-ion batteries are promising alternatives to Li-ion systems for electrochemical energy storage because of the higher natural abundance and widespread distribution of Na compared to Li. High capacity anode materials, such as phosphorus, have been explored to realize Na-ion battery technologies that offer comparable performances to their Li-ion counterparts. While P anodes provide unparalleled capacities, the mechanism of sodiation and desodiation is not well-understood, limiting further optimization. Here, we use a combined experimental and theoretical approach to provide molecular-level insight into the (de)sodiation pathways in black P anodes for sodium-ion batteries. A determination of the P binding in these materials was achieved by comparing to structure models created via species swapping, ab initio random structure searching, and a genetic algorithm. During sodiation, analysis of 31P chemical shift anisotropies in NMR data reveals P helices and P at the end of chains as the primary structural components in amorphous Na xP phases. X-ray diffraction data in conjunction with variable field 23Na magic-angle spinning NMR support the formation of a new Na3P crystal structure (predicted using density-functional theory) on sodiation. During desodiation, P helices are re-formed in the amorphous intermediates, albeit with increased disorder, yet emphasizing the pervasive nature of this motif. The pristine material is not re-formed at the end of desodiation and may be linked to the irreversibility observed in the Na-P system.