Many plants have natural partnerships with microbes that can boost their nitrogen (N) and/or phosphorus (P) acquisition. To assess whether wheat may have undiscovered associations of these types, we tested if N/P-starved Triticum aestivum show microbiome profiles that are simultaneously different from those of N/P-amended plants and those of their own bulk soils. The bacterial and fungal communities of root, rhizosphere, and bulk soil samples from the Historical Dryland Plots (Lethbridge, Canada), which hold T. aestivum that is grown both under N/P fertilization and in conditions of extreme N/P-starvation, were taxonomically described and compared (bacterial 16S rRNA genes and fungal Internal Transcribed Spacers-ITS). As the list may include novel N- and/or P-providing wheat partners, we then identified all the operational taxonomic units (OTUs) that were proportionally enriched in one or more of the nutrient starvation- and plant-specific communities. These analyses revealed: a) distinct N-starvation root and rhizosphere bacterial communities that were proportionally enriched, among others, in OTUs belonging to families Enterobacteriaceae, Chitinophagaceae, Comamonadaceae, Caulobacteraceae, Cytophagaceae, Streptomycetaceae, b) distinct N-starvation root fungal communities that were proportionally enriched in OTUs belonging to taxa Lulworthia, Sordariomycetes, Apodus, Conocybe, Ascomycota, Crocicreas, c) a distinct P-starvation rhizosphere bacterial community that was proportionally enriched in an OTU belonging to genus Agrobacterium, and d) a distinct P-starvation root fungal community that was proportionally enriched in OTUs belonging to genera Parastagonospora and Phaeosphaeriopsis. Our study might have exposed wheat-microbe connections that can form the basis of novel complementary yield-boosting tools.