Widespread degradation of Mongolian grasslands by overgrazing is of global concern. The objective of this study was to reveal the effects of grazing on pollination as an example of interaction biodiversity in Mongolian grasslands. We established three plots according to grazing intensity on the eastern steppe of Mongolia. In each plot, we recorded the numbers of insect-pollinated plants and observed the foraging behavior of pollinators in June and August. The richness of insect-pollinated species was high and these species were most abundant in lightly grazed plots, and formed complex relations with diverse pollinators. But, frequency of flower visitation and pollination index were greater in heavily grazed plots. All pollination properties were poorest in intermediately grazed plots. These results suggest that the forb-biased foraging of sheep and goats reduces the floral diversity of insect-pollinated species, and consequently reduces pollinators in the intermediately grazed plots. In the heavily grazed plots, only limited ruderal species could survive under heavy cattle grazing, and such simple vegetation formed unbalanced but strong bonds with pollinators. Removal simulation showed that the mutual network was more fragile with respect to the extinction of certain species.