Collective behaviors are widespread in nature and usually assumed to be strongly shaped by natural selection. However, the degree to which variation in collective behavior is heritable and has fitness consequences -- the two prerequisites for evolution by natural selection -- is largely unknown. We used a new pharaoh ant ( Monomorium pharaonis ) mapping population to estimate the heritability, genetic correlations, and fitness consequences of three collective behaviors (foraging, aggression, and exploration) as well as body size, sex ratio, and caste ratio. Heritability estimates for the collective behaviors were moderate, ranging from 0.17 to 0.32, but lower than our estimates for the heritability of caste ratio, sex ratio, and the body size of new workers, queens, and males. Moreover, variation among colonies in collective behaviors was phenotypically correlated, suggesting that selection may shape multiple colony collective behaviors simultaneously. Finally, we found evidence for directional selection that was similar in strength to estimates of selection in natural populations. Altogether, our study begins to elucidate the genetic architecture of collective behavior and is one of the first studies to demonstrate that it is shaped by selection.