Background. The genus Pachypodium contains 21 species of succulent, generally spinescent shrubs and trees found in southern Africa and Madagascar. Pachypodium has diversified mostly into arid and semi-arid habitats of Madagascar, and has been cited as an example of a plant group that links the highly diverse arid-adapted floras of Africa and Madagascar. However, a lack of knowledge about phylogenetic relationships within the genus has prevented testing of this and other hypotheses about the group. Methodology/Principal Findings. We use DNA sequence data from the nuclear ribosomal ITS and chloroplast trnL-F region for all 21 Pachypodium species to reconstruct evolutionary relationships within the genus. We compare phylogenetic results to previous taxonomic classifications and geography. Results support three infrageneric taxa from the most recent classification of Pachypodium, and suggest that a group of African species (P. namaquanum, P. succulentum and P. bispinosum) may deserve taxonomic recognition as an infrageneric taxon. However, our results do not resolve relationships among major African and Malagasy lineages of the genus. Conclusions/Significance. We present the first molecular phylogenetic analysis of Pachypodium. Our work has revealed five distinct lineages, most of which correspond to groups recognized in past taxonomic classifications. Our work also suggests that there is a complex biogeographic relationship between Pachypodium of Africa and Madagascar.