The antifreeze glycoprotein-fortified Antarctic notothenioid fishes comprise the predominant fish suborder in the isolated frigid Southern Ocean. Their ecological success undoubtedly entailed evolutionary acquisition of a full suite of cold-stable functions besides antifreeze protection. Prior studies of adaptive changes in these teleost fishes generally examined a single genotype or phenotype. We report here the genome-wide investigations of transcriptional and genomic changes associated with Antarctic notothenioid cold adaptation. We sequenced and characterized 33,560 ESTs from four tissues of the Antarctic notothenioid Dissostichus mawsoni and derived 3,114 nonredundant protein gene families and their expression profiles. Through comparative analyses of same-tissue transcriptome profiles of D. mawsoni and temperate/tropical teleost fishes, we identified 177 notothenioid protein families that were expressed many fold over the latter, indicating cold-related up-regulation. These up-regulated gene families operate in protein biosynthesis, protein folding and degradation, lipid metabolism, antioxidation, antiapoptosis, innate immunity, choriongenesis, and others, all of recognizable functional importance in mitigating stresses in freezing temperatures during notothenioid life histories. We further examined the genomic and evolutionary bases for this expressional up-regulation by comparative genomic hybridization of DNA from four pairs of Antarctic and basal non-Antarctic notothenioids to 10,700 D. mawsoni cDNA probes and discovered significant to astounding (3- to >300-fold, P < 0.05) Antarctic-specific duplications of 118 protein-coding genes, many of which correspond to the up-regulated gene families. Results of our integrative tripartite study strongly suggest that evolution under constant cold has resulted in dramatic genomic expansions of specific protein gene families, augmenting gene expression and gene functions contributing to physiological fitness of Antarctic notothenioids in freezing polar conditions.