Using first principles structure searching with density-functional theory (DFT) we identify a novel $Fmbar{3}m$ phase of Cu$_2$P and two low-lying metastable structures, an $Ibar{4}3d$--Cu$_3$P phase, and a $Cm$--Cu$_3$P$_{11}$ phase. The computed pair distribution function of the novel $Cm$--Cu$_3$P$_{11}$ phase shows its structural similarity to the experimentally identified $Cm$--Cu$_2$P$_7$ phase. The relative stability of all Cu--P phases at finite temperatures is determined by calculating the Gibbs free energy using vibrational effects from phonon modes at 0 K. From this, a finite-temperature convex hull is created, on which $Fmbar{3}m$--Cu$_2$P is dynamically stable and the Cu$_{3-x}$P ($x < 1$) defect phase $Cmc2_1$--Cu$_8$P$_3$ remains metastable (within 20 meV/atom of the convex hull) across a temperature range from 0 K to 600 K. Both CuP$_2$ and Cu$_3$P exhibit theoretical gravimetric capacities higher than contemporary graphite anodes for Li-ion batteries; the predicted Cu$_2$P phase has a theoretical gravimetric capacity of 508 mAh/g as a Li-ion battery electrode, greater than both Cu$_3$P (363 mAh/g) and graphite (372 mAh/g). Cu$_2$P is also predicted to be both non-magnetic and metallic, which should promote efficient electron transfer in the anode. Cu$_2$Ps favorable properties as a metallic, high-capacity material suggest its use as a future conversion anode for Li-ion batteries; with a volume expansion of 99% during complete cycling, Cu$_2$P anodes could be more durable than other conversion anodes in the Cu--P system with volume expansions greater than 150%.