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 genetic diversity, outcrossing rate and realized 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 the introduced Apis mellifera (Apidae). 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. Honeyeater exclusion did not significantly impact pollen dispersal or plant mating at Mount Caroline. In contrast, at the Chiddarcooping site, the exclusion of honeyeaters led to lower outcrossing rates, a threefold reduction in the average number of sires per fruit, a decrease in intermediate-distance mating and an increase in near-neighbour mating. The results from Chiddarcooping suggest that bird pollination may increase paternal genetic diversity, potentially leading to higher fitness of progeny and favouring the evolution of this strategy. However, further experimentation involving additional trees and study sites is required to test this hypothesis. Alternatively, insects may be effective pollinators in some populations of bird-adapted plants, but ineffective in others.