Land-use change and global warming are important factors driving bee decline, but it is largely unknown whether these drivers have resulted in changes in the life-history traits of bees. Recent studies have shown a stronger population decline of large- than small-bodied bee species, suggesting there may have been selective pressure on large, but not on small species to become smaller. Here we test this hypothesis by analyzing trends in bee body size of 18 Dutch species over a 147-year period using specimens from entomological collections. Large-bodied female bees shrank significantly faster than small-bodied female bees (6.5% and 0.5% respectively between 1900 and 2010). Changes in temperature during the flight period of bees did not influence the size-dependent shrinkage of female bees. Male bees did not shrink significantly over the same time period. Our results could imply that under conditions of declining habitat quantity and quality it is advantageous for individuals to be smaller. The size and sex-dependent responses of bees point towards an evolutionary response but genetic studies are required to confirm this. The declining body size of the large bee species that currently dominate flower visitation of both wild plants and insect-pollinated crops may have negative consequences for pollination service delivery.