Flexibility in behavior is thought to enable evolutionary success and can shape the ecology and possibly the evolution of mutualist partners. Bees foraging on flowers constitute a model mutualism for studying the consequences of behavioral flexibility. We show that flexibility in pollen extraction behavior by bees involves switching between two behaviors: scrabbling (involving vigorous leg movements) and buzzing (involving powerful thoracic vibrations). This behavioral flexibility benefits the bee, increasing their rate of pollen collection. Surprisingly, this behavioral flexibility simultaneously reduces bees’ effectiveness as pollinators, with buzzing bees transferring less pollen than scrabbling bees. Over evolutionary timescales, we also find that behavioral flexibility in pollen extraction behavior evolved early and repeatedly (~45 independent origins) in bees and may be a key driver of evolutionary diversification in bees. This behavioral flexibility has likely also driven the extraordinarily repeated evolution (>200 independent origins) of pollen concealment via tube-like anthers or corollas (i.e., poricidal floral morphology), which occur in >635 genera of flowering plant species (27,000 species, or 10% of all angiosperm species). However, we also find that poricidal plant species diversify more slowly and more frequently transition away from poricidal morphology, potentially a result of ecological consequences mentioned above. Altogether, our results suggest that the ecological effects of flexibility in behavior can have far reaching consequences for the evolution of mutualist partners.