Ecosystem services provided by mobile agents are increasingly threatened by the loss and modification of natural habitats and by climate change, risking the maintenance of biodiversity, ecosystem functions, and human welfare. Research oriented towards a better understanding of the joint effects of land use and climate change over the provision of specific ecosystem services is therefore essential to safeguard such services. Here we propose a methodological framework, which integrates species distribution forecasts and graph theory to identify key conservation areas, which if protected or restored could improve habitat connectivity and safeguard ecosystem services. We applied the proposed framework to the provision of pollination services by a tropical stingless bee (Melipona quadrifasciata), a key pollinator of native flora from the Brazilian Atlantic Forest and important agricultural crops. Based on the current distribution of this bee and that of the plant species used to feed and nest, we projected the joint distribution of bees and plants in the future, considering a moderate climate change scenario (following IPPC). We then used this information, the bee's flight range, and the current mapping of Atlantic Forest remnants to infer habitat suitability and quantify local and regional habitat connectivity for 2030, 2050 and 2080. Our results revealed north to south and coastal to inland shifts in the pollinator distribution during the next 70 years. Current and future connectivity maps unraveled the most important corridors, which if protected or restored, could facilitate the dispersal and establishment of bees during distribution shifts. Our results also suggest that coffee plantations from eastern São Paulo and southern Minas Gerais States could suffer a pollinator deficit in the future, whereas pollination services seem to be secured in southern Brazil. Landowners and governmental agencies could use this information to implement new land use schemes. Overall, our proposed methodological framework could help design novel conservational and agricultural practices that can be crucial to conserve ecosystem services by buffering the joint effect of habitat configuration and climate change.