Large-scale spatial variability in plant-pollinator communities (e.g., along geographic gradients, across different landscapes) is relatively well understood. However, we know much less about how these communities vary at small scales within a uniform landscape. Plants are sessile and highly sensitive to microhabitat conditions, whereas pollinators are highly mobile and, for the most part, display generalist feeding habits. Therefore, we expect plants to show greater spatial variability than pollinators. We analysed the spatial heterogeneity of a community of flowering plants and their pollinators in 40 plots across a 40-Km2 area within an uninterrupted Mediterranean scrubland. We recorded 3577 pollinator visits to 49 plant species. The pollinator community (170 species) was strongly dominated by honey bees (71.8% of the visits recorded). Flower and pollinator communities showed similar beta-diversity, indicating that spatial variability was similar in the two groups. We used path analysis to establish the direct and indirect effects of flower community distribution and honey bee visitation rate (a measure of the use of floral resources by this species) on the spatial distribution of the pollinator community. Wild pollinator abundance was positively related to flower abundance. Wild pollinator visitation rate was negatively related to flower abundance, suggesting that floral resources were not limiting. Pollinator and flower richness were positively related. Pollinator species composition was weakly related to flower species composition, reflecting the generalist nature of flower-pollinator interactions and the opportunistic nature of pollinator flower choices. Honey bee visitation rate did not affect the distribution of the wild pollinator community. Overall, we show that, in spite of the apparent physiognomic uniformity, both flowers and pollinators display high levels of heterogeneity, resulting in a mosaic of idiosyncratic local communities. Our results provide a measure of the background of intrinsic heterogeneity within a uniform habitat, with potential consequences on low-scale ecosystem function and microevolutionary patterns.