Understanding microbial nutritional requirements is a key challenge in microbiology. Here we leverage the recent availability of thousands of automatically generated genome-scale metabolic models to develop a predictor of microbial minimal medium requirements, which we apply to thousands of species to study the relationship between their nutritional requirements and their ecological and genomic traits. We first show that nutritional requirements are more similar among species that co-habit many ecological niches. We then reveal three fundamental characteristics of microbial fastidiousness (i.e., complex and specific nutritional requirements): (1) more fastidious microorganisms tend to be more ecologically limited; (2) fastidiousness is positively associated with smaller genomes and smaller metabolic networks; and (3) more fastidious species grow more slowly and have less ability to cooperate with other species than more metabolically versatile organisms. These associations reflect the adaptation of fastidious microorganisms to unique niches with few cohabitating species. They also explain how non-fastidious species inhabit many ecological niches with high abundance rates. Taken together, these results advance our understanding microbial nutrition on a large scale, by presenting new nutrition-related associations that govern the distribution of microorganisms in nature.