Charles Darwin posited two alternative hypotheses to explain the success of nonnative species based on their relatedness to natives: nonnative species that are closely related to native species could experience (1) higher invasion success because of an increased probability of habitat suitability (conferred by trait similarity) or (2) lower invasion success due to biotic interference, such as competition and limiting similarity. The paradox raised by the opposing predictions of these two hypotheses has been termed Darwin's naturalization conundrum{''} (DNC). Using plant communities measured repeatedly across an experimental fire gradient in an oak savanna (Minnesota, USA) over 31 yr, we evaluated the DNC by incorporating taxonomic, functional, and phylogenetic information. We used a focal-species{''} approach, in which the taxonomic, functional, and phylogenetic structure of species co-occurring with a given nonnative (focal) species in local communities was quantified. We found three main results: first, nonnative species tended to co-occur most with closely related natives, except at the extreme ends of the fire gradient (i.e., in communities with no fire and those subjected to high fire frequencies); second, with increasing fire frequency, nonnative species were functionally more similar to native species in recipient communities; third, functional similarity between co-occurring nonnatives and natives was stable over time, but their phylogenetic similarity was not, suggesting that dynamic external forces (e.g., climate variability) influenced the phylogenetic relatedness of nonnatives to natives. Our results provide insights for understanding invasion dynamics across environmental gradients and highlight the importance of evaluating different dimensions of biodiversity in order to draw stronger inferences regarding species co-occurrence at different spatial and temporal scales.