Aureococcus anophagefferens causes economically and ecologically destructive “brown tides” in the United States, China and South Africa. Here we report the 370,920 bp genomic sequence of AaV, a virus capable of infecting and lysing A. anophagefferens. AaV is a member of the nucleocytoplasmic large DNA virus (NCLDV) group, harboring 377 putative coding sequences and 8 tRNAs. Despite being an algal virus, AaV shows no phylogenetic affinity to the Phycodnaviridae family, to which most algae-infecting viruses belong. Core gene phylogenies, shared gene content and genome-wide similarities suggest AaV is the smallest member of the emerging clade “Megaviridae”. The genomic architecture of AaV demonstrates that the ancestral virus had an even smaller genome, which expanded through gene duplication and assimilation of genes from diverse sources including the host itself – some of which probably modulate important host processes. AaV also harbors a number of genes exclusive to phycodnaviruses – reinforcing the hypothesis that Phycodna- and Mimiviridae share a common ancestor.