Competing roles of coevolution, selective pressure and recombination are an emerging interest in virus evolution. We report a novel aviadenovirus from captive red-bellied parrots (Poicephalus rufiventris) that uncovers evidence of deep recombination among aviadenoviruses. The sequence identity of the virus was most closely related to Turkey adenovirus D (42% similarity) and other adenoviruses in chickens, turkeys and pigeons. Sequencing and comparative analysis showed that the genome comprised 40,930 nucleotides containing 42 predicted open reading frames (ORFs) 19 of which had strong similarity with genes from other adenovirus species. The new genome unveiled a lineage that likely participated in deep recombination events across the genus Aviadenovirus accounting for an ancient evolutionary relationship. We hypothesize frequent host switch events and recombination among adenovirus progenitors in Galloanserae hosts caused the radiation of extant aviadenoviruses and the newly assembled Poicephalus adenovirus genome points to a potentially broader host range of these viruses among birds.