Retroviruses can leave a "fossil record" in their hosts' genomes in the form of endogenous retroviruses. Foamy viruses, complex retroviruses that infect mammals, have been notably absent from this record. We have found an endogenous foamy virus within the genomes of sloths and show that foamy viruses were infecting mammals more than 100 million years ago and codiverged with their hosts across an entire geological era. Our analysis highlights the role of evolutionary constraint in maintaining viral genome structure and indicates that accessory genes and mammalian mechanisms of innate immunity are the products of macroevolutionary conflict played out over a geological time scale.