Following recent phylogenetic studies of the families and genera of Dioscoreales, the identification of monophylefic infrageneric taxa in the pantropical genus Dioscorea is a priority. A phylogenetic analysis based on sequence data from the plastid genes rbcL and matK is presented, using 67 species of Dioscorea and covering all the main Old World and selected New World lineages. The analysis used 14 outgroup taxa, including Trichopus Gaertn., Tacca J.R. & G. Forster, Stenomeris Planch., Burmannia L. and Thismia Griff. The main findings are: a) that a clade of rhizomatous taxa is sister to the rest of Dioscorea; b) the main Old World groups (such as the right-twining D. sect. Enantiophyllum) are monophylefic and c) there are two distinct lineages among the endemic Malagasy taxa. The consequences of the results for infrageneric classification of Dioscorea is considered, in particular the possibility of greatly simplifying the classifications of Knuth and Burkill. The results are also used to present novel hypotheses of character evolution in selected underground storage organ, inflorescence, fruit and seed characters and to discuss the origins of diversity in Dioscorea.