Notothenioids represent an adaptive radiation of teleost fishes in the frigid and ice-laden waters of the Southern Ocean surrounding Antarctica. Phylogenetic hypotheses for this clade have resulted primarily from analyses of mtDNA gene sequences, and studies utilizing nuclear gene DNA sequence data have focused on particular sub-clades of notothenioid fishes. In this study, we provide the first phylogenetic analysis of notothenioids using both mtDNA and nuclear gene sequences for a comprehensive sampling of all major lineages in the clade. Maximum parsimony and Bayesian analyses of aligned mtDNA genes, an aligned nuclear gene (S7 ribosomal protein intron 1), and combined dataset containing the mtDNA and nuclear genes resulted in phylogenies that contained the previously identified Antarctic and High Antarctic Clades. There were areas of agreement and disagreement between different datasets and methods of phylogenetic analysis, and the phylogenies resulting from the nuclear encoded S7 ribosomal protein intron 1 sequences were considerably less resolved than those inferred from mtDNA gene sequences. However, we anticipate increased resolution of the notothenioid phylogeny from future analyses that sample DNA sequences from several nuclear genes.