Phylogenetic relationships of sections and species within Corymbia (Myrtaceae), the bloodwood eucalypts, were evaluated by using combined analyses of nuclear rDNA (ETS + ITS) and morphological characters. Combining morphological characters with molecular data provided resolution of relationships within Corymbia. The analyses supported the monophyly of the genus and recognition of the following two major clades, treated here as new subgenera: subgenus Corymbia, including informal sections recognised by Hill and Johnson (1995), namely Rufaria (red bloodwoods), Apteria and Fundoria; and subgenus Blakella, including sections Politaria (spotted gums), Cadagaria, Blakearia (paper-fruited bloodwoods or ghost gums) and Ochraria (yellow bloodwoods). Hill and Johnson’s section Rufaria is monophyletic if Apteria and Fundoria are included. It is evident that, among the red bloodwoods, series are not monophyletic and several morphological characters result from convergent evolution. There was strong morphological and molecular evidence that the three species of red bloodwoods that occur in south-western Western Australia (series Gummiferae: C. calophylla and C. haematoxylon, and series Ficifoliae: C. ficifolia) form a monophyletic group, separate from the eastern C. gummifera (series Gummiferae), which is probably sister to the clade of all other red bloodwoods. Phylogenetic results supported recognition of new taxonomic categories within Corymbia, and these are formalised here.