Pollination by nectarivorous birds is predicted to result in different patterns of pollen dispersal and plant mating compared to pollination by insects. We tested the prediction that paternal diversity, outcrossing rate and realised pollen dispersal will be reduced when the primary pollinator group is excluded from bird-pollinated plants. Pollinator exclusion experiments in conjunction with paternity analysis of progeny were applied to Eucalyptus caesia Benth. (Myrtaceae), a predominantly honeyeater-pollinated tree that is visited by native insects and introduced honeybees. Microsatellite genotyping at 14 loci of all adult E. caesia at two populations (n = 580 and 315) followed by paternity analysis of 705 progeny revealed contrasting results between populations. At the Chiddarcooping site, the exclusion of honeyeaters led to lower outcrossing rates, a threefold reduction in the average number sires per fruit, a decrease in intermediate-distance mating, and an increase in near-neighbour mating. These findings suggest that bird pollination increases plant paternal diversity, potentially leading to higher fitness of progeny and favouring the evolution of this strategy. In contrast, honeyeater exclusion did not significantly impact pollen dispersal or plant mating at Mount Caroline, suggesting that insects may be effective pollinators in some populations of bird-adapted plants, but ineffective in others.