BACKGROUND: Little attention has been paid to the consequences of the last landbridge between Africa and Sicily on Mediterranean biogeography. Previous paleontological and scarce molecular data suggest possible faunal exchange later than the well-documented landbridge in the Messinian (5.3 My); however, a possible African origin of recent terrestrial Sicilian fauna has not been thoroughly tested with molecular methods. To gain insight into the phylogeography of the region, we examine two mitochondrial and two nuclear markers (one is a newly adapted intron marker) in green toads (Bufo viridis subgroup) across that sea barrier, the Strait of Sicily. RESULTS: Extensive sampling throughout the western Mediterranean and North Africa revealed a deep sister relationship between Sicilian (Bufo siculus n.sp.) and African green toads (B. boulengeri) on the mitochondrial and nuclear level. Divergence times estimated under a Bayesian-coalescence framework (mtDNA control region and 16S rRNA) range from the Middle Pliocene (3.6 My) to Pleistocene (0.16 My) with an average (1.83 to 2.0 My) around the Pliocene/Pleistocene boundary, suggesting possible land connections younger than the Messinian (5.3 My). We describe green toads from Sicily and some surrounding islands as a new endemic species (Bufo siculus). Bufo balearicus occurs on some western Mediterranean islands (Corsica, Sardinia, Mallorca, and Menorca) and the Apennine Peninsula, and is well differentiated on the mitochondrial and nuclear level from B. siculus as well as from B. viridis (Laurenti), whose haplotype group reaches northeastern Italy, north of the Po River. Detection of Calabrian B. balearicus haplotypes in northeastern Sicily suggests recent invasion. Our data agree with paleogeographic and fossil data, which suggest long Plio-Pleistocene isolation of Sicily and episodic Pleistocene faunal exchange across the Strait of Messina. It remains unknown whether both species (B. balearicus, B. siculus) occur in sympatry in northern Sicily. CONCLUSION: Our findings on green toads give the first combined mitochondrial and nuclear sequence evidence for a phylogeographic connection across the Strait of Sicily in terrestrial vertebrates. These relationships may have implications for comparative phylogeographic research on other terrestrial animals co-occurring in North Africa and Sicily.