Acacia ants evolved obligate protective mutualisms with acacia trees, which they defend against herbivores, food parasites and encroaching vegetation. In this mutualism, the fitness of one partner entirely depends on the other. Other ant species are parasitic on acacia trees; they nest on the tree, harvest food rewards, do not defend their own tree, and occasionally try to steal food from other trees, usually inhabited by mutualistic ants. To understand the behavioral and anatomical effects of the interaction between ants and host trees, I integrated brain anatomy, morphology and field experiments to study parasitic and mutualistic species of Pseudomyrmex ants associated with acacia trees. In Chapter 1, I describe a previously unknown behavior of stealing food from other ant-defended acacia trees in the parasitic acacia ant P. nigropilosus, and I evaluate four strategies that may allow parasitic ants to overcome the usually effective defenses of the robbed mutualistic ants protecting a host tree. In Chapter 2, I study how colony size correlates with the degree of division of labor and brain anatomy of workers, focusing on a species of acacia ant lacking morphological castes among workers, P. spinicola. In Chapter 3, I study acacia-ant behavior of killing vegetation encroaching on a host tree. I document the interspecific differences among acacia ants in the size of the area around the host tree that workers clear from encroaching vegetation. I further test for interspecific variation in pruning behavior, and whether mandibular force correlate with worker pruning decisions. In Chapter 4, I test whether ant species that routinely leave the host tree to forage or to prune encroaching vegetation are better at orienting themselves when returning to their host tree, compared to ant species that rarely leave their host tree. This dissertation documents how the obligate protective mutualism of an ant with a tree has consequences for division of labor, navigational skills, behavioral specializations, head shape and brain anatomy of ant workers. / text