Tripartite interactions between legumes and their root symbionts (rhizobia and arbuscular mycorrhizal fungi, AMF) are poorly understood, although it is well established that only specific combinations of symbionts lead to optimal plant growth. A classic example in which to investigate such interactions is the Brazilian legume tree Piptadenia gonoacantha (Caesalpinioideae), for which efficient nodulation has been described as dependent on the presence of AMF symbiosis. In this study, we compared the nodulation behaviour of several rhizobial strains with or without AMF inoculation, and performed analyses on nodulation, nodule cytology, N-fixing efficiency, and plant growth response. Nodulation of P. gonoacantha does not rely on the presence of AMF, but mycorrhization was rhizobial strain-dependent, and nodule effectiveness and plant growth were dependent on the presence of specific combinations of rhizobial strains and AMF. The co-occurrence of both symbionts within efficient nodules and the differentiation of bacteroids within nodule cells were also demonstrated. Novel close interactions and interdependency for the establishment and/or functioning of these symbioses were also revealed in Piptadenia, thanks to immunocytochemical analyses. These data are discussed in terms of the evolutionary position of the newly circumscribed mimosoid clade within the Caesalpinioid subfamily and its relative proximity to non-nodulated (but AMF-associated) basal subfamilies.