Populations of the mangrove Avicennia marina in the Sydney region exist as stands of varying size, reflecting both natural and anthropogenic fragmentation. We hypothesised that, as observed in many terrestrial forests, small stands (plants) would experience lower pollinator densities and altered pollinator behaviour and visitation and, in consequence, would display reduced pollen deposition as compared with large stands (>10,000 plants). Nevertheless, we recognise that such predictions may be overly simplistic because within this region A. marina attracts a diversity of flower visitors, but its only significant pollinator is the exotic honeybee Apis mellifera. Moreover, it is unclear how readily A. mellifera moves among groups of plants within different mangrove stands of varying sizes separated either by water or urban habitat matrix. Our detailed surveys within pairs of large and small stands in two locations support the predictions that pollinator density and pollen deposition are reduced or altered within small stands. Within small stands honeybee abundance and pollen deposition were on average reduced significantly by 84 and 61 %, respectively. Moreover, within small stands there was a non-significant 12 % increase in the mean time that honeybees spent foraging on individual plants and hence potentially depositing self pollen. Taken together, our data indicate that fragmentation affects the performance of A. mellifera as a pollinator of A. marina and reduce pollinator abundance, leading to pollen limitation in small as compared to large stands, which may negatively affect reproductive output.