Dating population divergence within species from molecular data and relating such dating to climatic and biogeographic changes is not trivial. Yet it can help formulating evolutionary hypotheses regarding local adaptation and future responses to changing environments. Key issues include statistical selection of a demographic and historical scenario among a set of possible scenarios, and estimation of the parameter(s) of interest under the chosen scenario. Such inferences greatly benefit from (i) independent information on evolutionary rate and pattern at genetic markers and (ii) new statistical approaches, such as approximate Bayesian computation - Random Forest (ABC-RF), which provides reliable inference at a low computational cost and the possibility to measure prediction quality at the exact position of the observed dataset. Here, we show full potential of the ABC-RF approach including prior knowledge on microsatellite genetic markers to decipher the evolutionary history of the African arid-adapted pest locust, Schistocerca gregaria, with support for a southern colonization of Africa, from a low number of founders of northern origin, dating back 2.6 Ky (90% CI: 0.9 – 6.6 Ky). We verify that this divergence time estimate accurately reflected true divergence time values by computing accuracy at a local posterior scale from simulated pseudo-observed datasets. The inferred divergence history is better explained by the peculiar biology of S. gregaria, which involves a density-dependent swarming phase with some exceptional spectacular migrations, rather than a continuous colonization resulting from the continental expansion of open vegetation habitats during more ancient Quaternary glacial climatic episodes.