Optimal foraging behaviour by nectavores is expected to result in a leptokurtic pollen dispersal distribution and predominantly near-neighbour mating. However, complex social interactions among nectarivorous birds may result in different mating patterns to those typically observed in insect-pollinated plants. Mating system, realised pollen dispersal and spatial genetic structure were examined in the bird-pollinated Eucalyptus caesia, a species characterised by small, geographically disjunct populations. Nine microsatellite markers were used to genotype an entire adult stand and 181 seeds from 28 capsules collected from 6 trees. Mating system analysis using MLTR revealed moderate to high outcrossing (tm=0.479-0.806) and low estimates of correlated paternity (rp=0.136±s.e. 0.048). Paternity analysis revealed high outcrossing rates (mean=0.72) and high multiple paternity, with 64 different sires identified for 181 seeds. There was a significant negative relationship between the frequency of outcross mating and distance between mating pairs. Realised mating events were more frequent than expected with random mating for plants <40 m apart. The overall distribution of pollen dispersal distances was platykurtic. Despite extensive pollen dispersal within the stand, three genetic clusters were detected by STRUCTURE analysis. These genetic clusters were strongly differentiated yet geographically interspersed, hypothesised to be a consequence of rare recruitment events coupled with extreme longevity. We suggest that extensive polyandry and pollen dispersal is a consequence of pollination by highly mobile honeyeaters and may buffer E. caesia against the loss of genetic diversity predicted for small and genetically isolated populations.