Hypotheses about the worldwide colonization routes of the melon fly, Zeugodacus cucurbitae (Diptera: Tephritidae), are mainly based on sparse historical records. Here we aim at reconstructing the colonization history of the African continent based on an improved description of the population structure of Z. cucurbitae and approximate Bayesian analyses. Individuals of Z. cucurbitae were sampled in 17 localities from East, West and Central Africa and genotyped at 19 microsatellite markers. Bayesian analyses showed intracontinental population structuring with populations from Uganda diverging from those of Tanzania and populations from Burundi and Kenya showing traces of admixture with West African samples. Approximate Bayesian Computation provided support to the hypothesis of a single introduction Z. cucurbitae into East Africa and subsequent expansion to West Africa, each colonization event was followed by a bottleneck that promoted population divergence within Africa. Parameter estimates suggested that these events are roughly compatible with the historical records of Z. cucurbitae presence in sub-Saharan Africa (viz. 1936 in East Africa and 1999 in West Africa) and allow excluding alternative hypotheses on older or multiple introductions of Z. cucurbitae.