In this study, we describe the detection of novel paramyxoviruses from the Eidolon helvum species of fruit bats. We extracted RNA from 312 spleen samples from bats captured in Zambia over a period of 4 years (2008-2011). Semi-nested RT-PCR detected a total of 25 (8%) positive samples for paramyxoviruses which were then directly sequenced and analyzed using phylogenetic analysis. Among the positive samples, seven novel paramyxoviruses were detected. Five viruses were closely related to the genus Henipavirus, while two viruses were related to the unclassified Bat paramyxoviruses from Ghana and Congo Brazzaville. Our study identified novel Henipavirus-related and unrelated viruses using RT-PCR in fruit bats from Kansaka National Park and indicated the presence of similar Bat paramyxoviruses originating from wide geographic areas, suggesting the ability of bats to harbor and transmit viruses. The presence of these viruses in fruit bats might pose a public health risk.