Plants and their microbial symbionts are often found to interact non-randomly in nature, but we have yet to understand the mechanisms responsible for such preferential species associations. Theory predicts that host plants should select symbiotic partners bearing traits complementary to their own, as this should favor cooperation and evolutionary stability of mutualisms. Here, we present the first field-based empirical test for this hypothesis using arbuscular mycorrhizas (AM), the oldest and most widespread plant symbiosis. Preferential associations occurring within a local plant–AM fungal community could not be predicted by the spatial distributions of interacting partners, nor by gradients in soil properties. Rather, plants with similar traits preferentially hosted similar AM fungi and, likewise, phylogenetically related AM fungi (assumed to have similar functional traits) interacted with similar plants. Our results suggest that trait-based partner selection may have been a strong force in maintaining plant–AM fungal symbioses since the evolution of land plants.