Division of labor is a complex phenomenon observed throughout nature. Theoretical studies have focused either on its emergence through self-organization mechanisms or on its adaptive consequences. We suggest that the interaction of self-organization, which undoubtedly characterizes division of labor in social insects, and evolution should be further explored. We review the factors empirically shown to influence task choice. In light of these factors, we review the most important self-organization and evolutionary models for division of labor and outline their advantages and limitations. We describe ways to unify evolution and self-organization in the theoretical study of division of labor and recent results in this area. Finally, we discuss some benchmarks and primary challenges of this approach.