Collective foraging confers benefits in terms of reduced predation risk and access to social information, but it heightens local competition when resources are limited. In social insects, resource limitation has been suggested as a possible cause for the typical decrease in per capita productivity observed with increasing colony size, a phenomenon known as Michener's paradox. Polydomy (distribution of a colony's brood and workers across multiple nests) is believed to help circumvent this paradox through its positive effect on foraging efficiency, but there is still little supporting evidence for this hypothesis. Here, we show experimentally that polydomy enhances the foraging performance of food-deprived Temnothorax nylanderi ant colonies via several mechanisms. First, polydomy influences task allocation within colonies, resulting in faster retrieval of protein resources. Second, communication between sister nests reduces search times for far away resources. Third, colonies move queens, brood and workers across available nest sites in response to spatial heterogeneities in protein and carbohydrate resources. This suggests that polydomy represents a flexible mechanism for space occupancy, helping ant colonies adjust to the environment.