A phylogeny of the fungal phylum Basidiomycota is presented based on a survey of 160 taxa and five nuclear genes. Two genes, rpb2, and tef1, are presented in detail. The rpb2 gene is more variable than tef1 and recovers well-supported clades at shallow and deep taxonomic levels. The tef1 gene recovers some deep and ordinal-level relationships but with greater branch support from nucleotides compared to amino acids. Intron placement is dynamic in tef1, often lineage-specific, and diagnostic for many clades. Introns are fewer in rpb2 and tend to be highly conserved by position. When both protein-coding loci are combined with sequences of nuclear ribosomal RNA genes, 18 inclusive clades of Basidiomycota are strongly supported by Bayesian posterior probabilities and 16 by parsimony bootstrapping. These numbers are greater than produced by single genes and combined ribosomal RNA gene regions. Combination of nrDNA with amino acid sequences, or exons with third codon positions removed, produces strong measures of support, particularly for deep internodes of Basidiomycota, which have been difficult to resolve with confidence using nrDNA data alone. This study produces strong boostrap support and significant posterior probabilities for the first time for the following monophyletic groups: (1) Ustilaginomycetes plus Hymenomycetes, (2) an inclusive cluster of hymenochaetoid, corticioid, polyporoid, Thelephorales, russuloid, athelioid, Boletales, and euagarics clades, (3) Thelephorales plus the polyporoid clade, (4) the polyporoid clade, and (5) the cantharelloid clade. Strong support is also recovered for the basal position of the Dacrymycetales in the Hymenomycetidae and paraphyly of the Exobasidiomycetidae.