The Polyomaviridae is a diverse family of circular double-stranded DNA viruses. Polyomaviruses have been isolated from a wide array of animal hosts. An understanding of the evolutionary and ecological dynamics of these viruses is essential to understanding the pathogenicity of polyomaviruses. Using a high throughput sequencing approach, we identified a novel polyomavirus in an emerald notothen (Trematomus bernacchii) sampled in the Ross sea (Antarctica), expanding the known number of fish-associated polyomaviruses. Our analysis suggests that polyomaviruses belong to three main evolutionary clades; the first clade is made up of all recognized terrestrial polyomaviruses. The fish-associated polyomaviruses are not monophyletic, and belong to two divergent evolutionary lineages. The fish viruses provide evidence that the evolution of the key viral large T protein involves gain and loss of distinct domains.