The substrates of the Brazilian campos rupestres, a grassland ecosystem, have extremely low concentrations of phosphorus and nitrogen, imposing restrictions to plant growth. Despite that, this ecosystem harbors almost 15% of the Brazilian plant diversity, raising the question of how plants acquire nutrients in such a harsh environment. Here, we set out to uncover the taxonomic profile, the compositional and functional differences and similarities, and the nutrient turnover potential of microbial communities associated with two plant species of the campos rupestres-dominant family Velloziaceae that grow over distinct substrates (soil and rock). Using amplicon sequencing data, we show that, despite the pronounced composition differentiation, the plant-associated soil and rock communities share a core of highly efficient colonizers that tend to be highly abundant and is enriched in 21 bacterial families. Functional investigation of metagenomes and 522 metagenome-assembled genomes revealed that the microorganisms found associated to plant roots are enriched in genes involved in organic compound intake, and phosphorus and nitrogen turnover. We show that potential for phosphorus transport, mineralization, and solubilization are mostly found within bacterial families of the shared microbiome, such as Xanthobacteraceae and Bryobacteraceae. We also detected the full repertoire of nitrogen cycle-related genes and discovered a lineage of Isosphaeraceae that acquired nitrogen-fixing potential via horizontal gene transfer and might be also involved in nitrification via a metabolic handoff association with Binataceae. We highlight that plant-associated microbial populations in the campos rupestres harbor a genetic repertoire with potential to increase nutrient availability and that the microbiomes of biodiversity hotspots can reveal novel mechanisms of nutrient turnover.