Understanding the diversity of henipaviruses and related viruses is important in determining the viral ecology within flying-fox populations and assessing the potential threat posed by these agents. This study sought to identify the abundance and diversity of previously unknown paramyxoviruses in Australian flying-fox species (Pteropus alecto, P. scapulatus, P. poliocephalus and P. conspicillatus) and in the Christmas Island species P. melanotus natalis. Using a degenerative RT-PCR specific for the L gene of known species of Henipavirus and two closely related paramyxovirus genera Respirovirus and Morbillivirus, we identified an abundance and diversity of previously unknown paramyxoviruses (UPV), with a representative 31 UPVs clustering in eight distinct groups (100 UPVs/495 samples). No new henipaviruses were identified. The findings are consistent with a hypothesis of co-evolution of paramyxoviruses and their flying-fox hosts. Quantification of the degree of co-speciation between host and virus would strengthen this hypothesis.