Allocation of labor to foraging is socially regulated in colonies of the honey bee, Apis mellifera, and the paper wasp, Polistes metricus. Reduced nutritional status also is a shared characteristic of foragers in many taxa of social Hymenoptera, including Apis and Polistes. However, eusociality evolved independently in the lineages represented by these two species, and they exhibit very different forms of social regulation of foraging behavior. We used an Apis/Polistes comparison to address a major issue in our understanding of genes and social behavior: the extent to which related, but distinct, forms of social behavior are influenced by common molecular pathways. We hypothesized that there are similar patterns of brain gene expression in Apis and Polistes foragers. To address this question on a genomic scale, we studied in P. metricus a set of 25 candidate genes previously associated with foraging in Apis, made possible by our new Polistes brain EST project. We examined candidate gene expression patterns in four P. metricus groups (workers, queens, gynes, and foundresses) that allowed us to separate the influences of foraging state and reproductive state. About half of the genes examined showed differences in gene expression associated with foraging state, while approximately one-third differed with reproductive state. Multivariate analysis of all genes combined indicated that gynes had the most distinct gene expression profiles, while there was substantial overlap among individuals in the other three groups, highlighting the roles of both foraging state and reproductive state on Polistes brain gene expression. These results demonstrate that a substantial subset of our candidate genes show expression differences related to colony organization in both Apis and Polistes, despite their independent origins of sociality and vastly different forms of division of labor.