The advent of molecular genetic techniques to assign parentage accurately in bird species has revolutionised the view of avian mating strategies. Australia has provided some exciting examples in this modern synthesis of mating strategies, yet there remains a clear bias towards species in the northern hemisphere. We present analyses of molecular assignment of paternity in two species of Australian honeyeater (Meliphagidae), which have only recently had their social mating systems described. We find extensive extra-pair paternity in both the Yellow-faced Honeyeater (Lichenostomus chrysops) and Crescent Honeyeater (Phylidonyris pyrrhopterus). Extra-pair paternity in both species is consistent with some predictions from behavioural observations, for example, extra-territory excursions by breeding females and non-aggressive behaviour of territorial males towards extra-pair females on their territories. In Yellow-faced Honeyeaters, however, there is substantial paternal care from social males, raising interesting questions as to the fitness advantages of differing reproductive tactics of males in this species.