The rarity of symbiotic nitrogen-fixing trees in higher-latitude compared to lower-latitude forests is paradoxical because higher-latitude soils are relatively N poor. Using national-scale forest inventories from the United States and Mexico, we show that the latitudinal abundance distribution of N-fixing trees (more than 10 times less abundant poleward of 35 degrees N) coincides with a latitudinal transition in symbiotic N-fixation type: rhizobial N-fixing trees (which are typically facultative, regulating fixation to meet nutritional demand) dominate equatorward of 35 degrees N, whereas actinorhizal N-fixing trees (typically obligate, maintaining fixation regardless of soil nutrition) dominate to the north. We then use theoretical and statistical models to show that a latitudinal shift in N-fixation strategy (facultative vs. obligate) near 35 degrees N can explain the observed change in N-fixing tree abundance, even if N availability is lower at higher latitudes, because facultative fixation leads to much higher landscape-scale N-fixing tree abundance than obligate fixation.