Nitrogen acquisition is a major challenge for herbivorous animals, and the repeated origins of herbivory across the ants have raised expectations that nutritional symbionts have shaped their diversification. Direct evidence for N provisioning by internally housed symbionts is rare in animals; among the ants, it has been documented for just one lineage. In this study we dissect functional contributions by bacteria from a conserved, multi-partite gut symbiosis in herbivorous Cephalotes ants through in vivo experiments, metagenomics, and in vitro assays. Gut bacteria recycle urea, and likely uric acid, using recycled N to synthesize essential amino acids that are acquired by hosts in substantial quantities. Specialized core symbionts of 17 studied Cephalotes species encode the pathways directing these activities, and several recycle N in vitro. These findings point to a highly efficient N economy, and a nutritional mutualism preserved for millions of years through the derived behaviors and gut anatomy of Cephalotes ants.