Population genetic structure is often used to infer population connectivity, but genetic structure may largely reflect historical rather than recent processes. We contrasted genetic structure with recent gene-flow estimates among 6 herds of African buffalo (Syncerus caffer) in the Caprivi Strip, Namibia, using 134 individuals genotyped at 10 microsatellite loci. We tested whether historical and recent gene flows were influenced by distance, potential barriers (rivers), or landscape resistance (distance from water). We also tested at what scales individuals were more related than expected by chance. Genetic structure across the Caprivi Strip was weak, indicating that historically, gene flow was strong and was not affected by distance, barriers, or landscape resistance. Our analysis of simulated data suggested that genetic structure would be unlikely to reflect human disturbances in the last 10–20 generations (75–150 years) because of slow predicted rates of genetic drift, but recent gene-flow estimates would be affected. Recent gene-flow estimates were not consistently affected by rivers or distance to water but showed that isolation by distance appears to be developing. Average relatedness estimates among individuals exceeded random expectations only within herds. We conclude that historically, African buffalo moved freely throughout the Caprivi Strip, whereas recent gene flow has been more restricted. Our findings support efforts to maintain the connectivity of buffalo herds across this region and demonstrate the utility of contrasting genetic inferences from different time scales.