Nitrogen-fixing symbiosis is globally important in ecosystem functioning and agriculture, yet the evolutionary history of nodulation remains the focus of considerable debate. Recent evidence suggesting a single origin of nodulation followed by massive parallel evolutionary losses raises questions about why a few lineages in the N2-fixing clade retained nodulation and diversified as stable nodulators, while most did not. Within legumes, nodulation is restricted to the two most diverse subfamilies, Papilionoideae and Caesalpinioideae, which show stable retention of nodulation across their core clades. We characterize two nodule anatomy types across 128 species in 56 of the 152 genera of the legume subfamily Caesalpinioideae: fixation thread nodules (FTs), where nitrogen-fixing bacteroids are retained within the apoplast in modified infection threads, and symbiosomes, where rhizobia are symplastically internalized in the host cell cytoplasm within membrane-bound symbiosomes (SYMs). Using a robust phylogenomic tree based on 997 genes from 147 Caesalpinioideae genera, we show that losses of nodulation are more prevalent in lineages with FTs than those with SYMs. We propose that evolution of the symbiosome allows for a more intimate and enduring symbiosis through tighter compartmentalization of their rhizobial microsymbionts, resulting in greater evolutionary stability of nodulation across this species-rich pantropical legume clade.