Adenoviruses (AdVs) are important human and animal pathogens and are frequently used as vectors for gene therapy and vaccine delivery. Surprisingly, there are only scant data regarding primate AdV origin and evolution, especially in the most basal primate hosts. We detect and sequence AdVs from faeces of two Madagascan lemur species. Complete genome sequence analyses define a new AdV species with a particularly large gene encoding a protein of unknown function in the early gene region 3. Unexpectedly, the new AdV species is not most similar to human or other simian AdVs but to bat adenovirus C. Genome characterisation shows signals of virus-host codivergence in non-structural genes, which show lower diversity than structural genes. Outside a lemur species mixing zone, recombination less frequently separates structural genes, as in human adenovirus C. The evolutionary history of lemur AdVs likely involves both a host switch and codivergence with the lemur hosts.