The flora on the afro-alpine sky islands is renowned for extreme fragmentation, representing a unique natural experiment in biogeography. Here we address the roles of isolation and gene flow, in particular across the narrow Rift Valley (the RV barrier) that cuts through the Ethiopian Highlands (EH), and across the vast low-lying landscape that separates EH from the East African mountains (the EH-EA barrier). We inferred the history of two species with different dispersal mechanisms, but with similar geographic ranges and habitats based on Amplified fragment length polymorphisms (AFLPs). Contrary to our predictions, we found that the populations from opposite sides of the RV barrier were less similar than those from opposite sides of the EH-EA barrier, and that only the supposedly short distance-dispersed species (Trifolium cryptopodium) showed a strong signal of secondary gene flow across the RV barrier. In the wind-dispersed Carduus schimperi, we rather found an evidence for the gene flow between differentiated populations inhabiting different EA mountains. Both species harbored little genetic diversity but considerable genetic rarity in several individual mountains, suggesting long-term isolation and bottlenecks during climatically unfavorable periods. Our genetic data corroborate a division of C. schimperi into three subspecies, but with new delimitation of their ranges, and of T. cryptopodium into two intraspecific taxa. Our findings support the idea that stochasticity may play a major role in shaping extremely fragmented ecosystems such as the afro-alpine. After initial colonization of different mountains, periods of isolation may alternate with unpredictable episodes of intermountain gene flow.