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 (Nucleocytoviricota) with dating analyses calibrated by known host taxa. 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 to animal hosts that led to the emergence of iridoviruses and African swine fever viruses within the last 400 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 history.