Viruses are widespread parasites with important impacts on public health, economy, and ecosystems. However, little is known about their origins, ages, and early evolutionary relationships with hosts. Here, we infer the maximum divergence times for eukaryotic giant DNA viruses (phylum Nucleocytoviricota) with dating analyses calibrated by host taxon ages of virus lineages with specific host ranges. The last common ancestor of Nucleocytoviricota existed after 1,000 million years ago, suggesting a much later origin than that of the eukaryotes. The early evolution of Nucleocytoviricota either coincided with or postdated a substantial increase in the oxygen levels on the Earth's surface during the Neoproterozoic Era. The lineage diversification of giant viruses was frequently associated with host shifts, including two major transitions from amoebozoan hosts to animal hosts that eventually led to the emergence of iridoviruses and African swine fever viruses within the last 450 million years. These results outline the evolutionary timescale of a major virus group and are pivotal for further understanding the virus-host interactions and their potential ecological roles in the Earth's history.