Several genetic and nongenetic hypotheses have been formulated to account for the evolution and maintenance of multiple mating by females (polyandry) in social Hymenoptera. A major hypothesis argues that polyandry allows production of genetically diverse workers varying in their inclination to perform different tasks, thereby enhancing division of labor and colony task efficiency. We tested the relationship between patriline, worker size, and task specialization in the ant Cataglyphis cursor, a species showing natural variation in queen mating frequency. Our results reveal a significant association between patriline and task preference: workers belonging to different patrilines differ in their propensity to perform a given task (foraging, nest construction, waste management, or food storage). Furthermore, we found that worker size is closely associated with task specialization but not with paternal origin. Overall, these results show that task performance is at least partly genetically influenced in the ant C. cursor, which is a key prerequisite for polyandry to improve division of labor in social insects.