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 (UPVs) in Australian flying-fox species (Pteropus alecto, Pteropus scapulatus, Pteropus poliocephalus and Pteropus conspicillatus) and in the Christmas Island species Pteropus melanotus natalis. Using a degenerative reverse transcription-PCR specific for the L gene of known species of the genus Henipavirus and two closely related paramyxovirus genera Respirovirus and Morbillivirus, we identified an abundance and diversity of previously UPVs, with a representative 31 UPVs clustering in eight distinct groups (100 UPVs/495 samples). No new henipaviruses were identified. The findings were 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 (beyond the scope of this study) would strengthen this hypothesis.