Adenoviruses (AdV) broadly infect vertebrate hosts including a variety of primates. We identified a novel AdV in the feces of captive gorillas by isolation in cell culture, electron microscopy and PCR. From the supernatants of infected cultures we amplified DNA polymerase (DPOL), preterminal protein (pTP) and hexon gene sequences with generic pan primate AdV PCR assays. The sequences in-between were amplified by long-distance PCRs of 2-10 kb length, resulting in a final sequence of 15.6 kb. Phylogenetic analysis placed the novel gorilla AdV into a cluster of primate AdVs belonging to the species Human adenovirus B (HAdV-B). Depending on the analyzed gene, its position within the cluster was variable. To further elucidate its origin, feces samples of wild gorillas were analyzed. AdV hexon sequences were detected which are indicative for three distinct and novel gorilla HAdV-B viruses, among them a virus nearly identical to the novel AdV isolated from captive gorillas. This shows that the discovered virus is a member of a group of HAdV-B viruses that naturally infect gorillas. The mixed phylogenetic clusters of gorilla, chimpanzee, bonobo and human AdVs within the HAdV-B species indicate that host switches may have been a component of the evolution of human and non-human primate HAdV-B viruses.