A comprehensive and meaningful phylogenetic hypothesis for the commercially important coffee genus (Coffea) has long been a key objective for coffee researchers. For molecular studies, progress has been limited by low levels of sequence divergence, leading to insufficient topological resolution and statistical support in phylogenetic trees, particularly for the major lineages and for the numerous species occurring in Madagascar. We report here the first almost fully resolved, broadly sampled phylogenetic hypothesis for coffee, the result of combining genotyping-by-sequencing (GBS) technology with a newly developed, lab-based workflow to integrate short read next-generation sequencing for low numbers of additional samples. Biogeographic patterns indicate either Africa or Asia (or possibly the Arabian Peninsula) as the most likely ancestral locality for the origin of the coffee genus, with independent radiations across Africa, Asia, and the Western Indian Ocean Islands (including Madagascar and Mauritius). The evolution of caffeine, an important trait for commerce and society, was evaluated in light of our phylogeny. High and consistent caffeine content is found only in species from the equatorial, fully humid environments of West and Central Africa, possibly as an adaptive response to increased levels of pest predation. Moderate caffeine production, however, evolved at least one additional time recently (between 2 and 4 Mya) in a Madagascan lineage, which suggests that either the biosynthetic pathway was already in place during the early evolutionary history of coffee, or that caffeine synthesis within the genus is subject to convergent evolution, as is also the case for caffeine synthesis in coffee versus tea and chocolate.