Nile crocodiles are apex predators widely distributed in sub-Saharan Africa that have been viewed and managed as a single species. A complex picture of broad and fine-scale phylogeographic patterns that includes the recognition of two species (Crocodylus niloticus and Crocodylus suchus), and the structuring of populations according to river basins has started to emerge. However, previous studies surveyed a limited number of samples and geographical regions, and large areas of the continent remained unstudied. This work aimed at a fine scale portrait of Nile crocodile populations at the fringes of their geographic distribution in southern Africa. Wild and captive individuals were sampled across four major river systems (Okavango, Lower Kunene, Lower Shire and Limpopo) and the KwaZulu-Natal region. A multi-marker approach was used to infer phylogeographic and genetic diversity patterns, including new and public mitochondrial data, and a panel of 11 nuclear microsatellites. All individuals belonged to a phylogenetic clade previously associated with the C. niloticus species, thus suggesting the absence of C. suchus in southern Africa. The distribution of mitochondrial haplotypes indicated ancestral genetic connectivity across large areas, with loss of diversity along the north-south axis. Genetic variation partitioned the populations primarily into western and eastern regions of southern Africa, and secondarily into the major river systems. Populations were partitioned into five main groups corresponding to the Lower Kunene, the Okavango, the Lower Shire, and the Limpopo rivers, and the KwaZulu-Natal coastal region. All groups show evidence of recent bottlenecks and small effective population sizes. Long-term genetic diversity is likely to be compromised, raising conservation concern. These results emphasize the need for local genetic assessment of wild populations of Nile crocodiles to inform strategies for management of the species in southern Africa.