The Brazilian Cerrado is the most diverse savanna in the world. Phylogeographical patterns for Cerrado tree species are relatively congruent; however, the causes of these patterns are not clear. Ours aims were to investigate phylogeographical patterns in two co-distributed Annona spp. in the Cerrado and identify the factors responsible for their genetic structure. We sequenced non-coding plastid DNA regions and estimated divergence times using a Bayesian Markov chain Monte Carlo method implemented in BEAST. Generalized linear mixed models (GLMMs) were used to relate genetic divergence with spatial, climatic and phytogeographic data. Annona crassiflora possessed only one haplotype, whereas A.coriacea possessed nine haplotypes constituting two groups: western and eastern. Haplotype diversification first occurred in the Pliocene; the split between eastern and western groups was dated to the Early Pleistocene. GLMMs detected a weak association of genetic distance with current climatic factors, represented mainly by precipitation in the warmest months. In A.coriacea, the north of central Cerrado (around Serra Geral de Goias) is suggested as a putative Pleistocene refugium. The current climate and dispersal and local adaptation processes probably contribute to maintaining the east-west genetic structure in A.coriacea. Both Annona spp. show idiosyncratic population histories, reminiscent of the complex biogeography of the Cerrado.