The black rhinoceros is again on the verge of extinction due to unsustainable poaching in its nativerange. Despite a wide historic distribution, the black rhinoceros was traditionally thought of asdepauperate in genetic variation, and with very little known about its evolutionary history. Thisknowledge gap has hampered conservation efforts because hunting has dramatically reduced thespecies' once continuous distribution, leaving five surviving gene pools of unknown genetic affinity.Here we examined the range-wide genetic structure of historic and modern populations using thelargest and most geographically representative sample of black rhinoceroses ever assembled. Usingboth mitochondrial and nuclear datasets, we described a staggering loss of 69% of the species'mitochondrial genetic variation, including the most ancestral lineages that are now absent frommodern populations. Genetically unique populations in countries such as Nigeria, Cameroon, Chad,Eritrea, Ethiopia, Somalia, Mozambique, Malawi and Angola no longer exist. We found that the historicrange of the West African subspecies (D. b. longipes), declared extinct in 2011, extends into southernKenya, where a handful of individuals survive in the Masai Mara. We also identify conservation unitsthat will help maintain evolutionary potential. Our results suggest a complete re-evaluation of currentconservation management paradigms for the black rhinoceros.