Hyenas (family Hyaenidae), as the sister group to cats (family Felidae), represent a deeply diverging branch within the cat-like carnivores (Feliformia). With an estimated population size of <10,000 individuals worldwide, the brown hyena (Parahyaena brunnea) represents the rarest of the four extant hyena species and has been listed as Near Threatened by the IUCN. Here, we report a high-coverage genome from a captive bred brown hyena and both mitochondrial and low-coverage nuclear genomes of 14 wild-caught brown hyena individuals from across southern Africa. We find that brown hyena harbor extremely low genetic diversity on both the mitochondrial and nuclear level, most likely resulting from a continuous and ongoing decline in effective population size that started ∼1 Ma and dramatically accelerated towards the end of the Pleistocene. Despite the strikingly low genetic diversity, we find no evidence of inbreeding within the captive bred individual and reveal phylogeographic structure, suggesting the existence of several potential subpopulations within the species.