Genetic studies concerned with the demographic history of wildlife species can help elucidate the role of climate change and other forces such as human activity in shaping patterns of divergence and distribution. The African buffalo (Syncerus caffer) declined dramatically during the rinderpest pandemic in the late 1800s, but little is known about the earlier demographic history of the species. We analysed genetic variation at 17 microsatellite loci and a 302-bp fragment of the mitochondrial DNA control region to infer past demographic changes in buffalo populations from East Africa. Two Bayesian coalescent-based methods as well as traditional bottleneck tests were applied to infer detailed dynamics in buffalo demographic history. No clear genetic signature of population declines related to the rinderpest pandemic could be detected. However, Bayesian coalescent modelling detected a strong signal of African buffalo population declines in the order of 75-98%, starting in the mid-Holocene (approximately 3-7000 years ago). The signature of decline was remarkably consistent using two different coalescent-based methods and two types of molecular markers. Exploratory analyses involving various prior assumptions did not seriously affect the magnitude or timing of the inferred population decline. Climate data show that tropical Africa experienced a pronounced transition to a drier climate approximately 4500 years ago, concurrent with the buffalo decline. We therefore propose that the mid-Holocene aridification of East Africa caused a major decline in the effective population size of the buffalo, a species reliant on moist savannah habitat for its existence.