Extra- and intracellular viruses in the biosphere outnumber their cellular hosts by at least one order of magnitude. How is this enormous domain of viruses organized? Sampling of the virosphere has been scarce and focused on viruses infecting humans, cultivated plants, and animals as well as those infecting well-studied bacteria. It has been relatively easy to cluster closely related viruses based on their genome sequences. However, it has been impossible to establish long-range evolutionary relationships as sequence homology diminishes. Recent advances in the evaluation of virus architecture by high-resolution structural analysis and elucidation of viral functions have allowed new opportunities for establishment of possible long-range phylogenic relationships-virus lineages. Here, we use a genomic approach to investigate a proposed virus lineage formed by bacteriophage PRD1, infecting gram-negative bacteria, and human adenovirus. The new member of this proposed lineage, bacteriophage Bam35, is morphologically indistinguishable from PRD1. It infects gram-positive hosts that evolutionarily separated from gram-negative bacteria more than one billion years ago. For example, it can be inferred from structural analysis of the coat protein sequence that the fold is very similar to that of PRD1. This and other observations made here support the idea that a common early ancestor for Bam35, PRD1, and adenoviruses existed.