BACKGROUND: The packaging, expression, and maintenance of nuclear genomes using histone proteins is a ubiquitous and fundamental feature of eukaryotic cells, yet the phylum Dinoflagellata has apparently abandoned this model of nuclear organization. Their nuclei contain permanently condensed, liquid crystalline chromosomes that seemingly lack histone proteins, and contain remarkably large genomes. The molecular basis for this reorganization is poorly understood, as is the sequence of evolutionary events that led to such radical change. We have investigated nuclear organization in the closest relative to dinoflagellates, Perkinsus marinus, and an early-branching dinoflagellate, Hematodinium sp., to identify early changes that occurred during dinoflagellate nuclear evolution. RESULTS: We show that P. marinus has a typical nuclear organization that is based on the four core histones. By the early divergence of Hematodinium sp., however, dinoflagellate genome size is dramatically enlarged, chromosomes are permanently condensed, and histones are scarcely detectable. In place of histones, we identify a novel, dominant family of nuclear proteins that is only found in dinoflagellates and, surprisingly, in a family of large algal viruses, the Phycodnaviridae. These new proteins, which we call DVNPs (dinoflagellate/viral nucleoproteins), are highly basic, bind DNA with similar affinity to histones, and occur in multiple posttranslationally modified forms. We find these proteins throughout all dinoflagellates, including early- and late-branching taxa, but not in P. marinus. CONCLUSIONS: Gain of a major novel family of nucleoproteins, apparently from an algal virus, occurred early in dinoflagellate evolution and coincides with rapid and dramatic reorganization of the dinoflagellate nucleus.