Charles Darwin posited two alternative hypotheses to explain the success of nonnative species based on their relatedness to incumbent natives: coexistence between them should be (i) more likely with greater relatedness (due to trait similarity that correlates with better matching to the environment), or (ii) less likely (due to biotic interference, such as competition). The paradox raised by the opposing predictions of these two hypotheses has been termed ‘Darwin’s naturalization conundrum’ (DNC). Using plant communities measured repeatedly over a 31-year time span across an experimental fire gradient in an oak savanna (Minnesota, USA) we evaluated the DNC by explicitly incorporating taxonomic, functional and phylogenetic information. Our approach was based on ‘focal-species’ such that the taxonomic, functional and phylogenetic structure of species co-occurring with a given nonnative species in local communities was quantified. We found three main results: first, nonnatives colonizers tended to co-occur most with closely related incumbent natives in recipient communities, except in the extreme ends of the fire gradient (i.e., 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 of co-occurring nonnatives and natives in recipient communities showed a consistent pattern over time, but the phylogenetic similarity shifted over time, suggesting that external forces (e.g., climate variability) are also relevant in driving the phylogenetic relatedness of nonnatives to natives in invaded communities. Our results provide insights for understanding the invasion dynamics across environmental gradients and highlight the importance of evaluating different dimensions of biodiversity in order to produce more powerful evaluations of species co-occurrence at different spatial and temporal scales.