The discrepancy between the pace of sequencing and functional characterization of genomes is a major challenge in understanding complex microbial metabolic processes and metabolic interactions in the environment. Here, we identified and validated genes related to the utilization of specific metabolites in bacteria by profiling metabolite utilization in libraries of mutant strains. Untargeted mass spectrometry based metabolomics was used to identify metabolites utilized by Escherichia coli and Shewanella oneidensis MR-1. Targeted high-throughput metabolite profiling of spent media of 8042 individual mutant strains was performed to link utilization to specific genes. Using this approach we identified genes of known function as well as novel transport proteins and enzymes required for the utilization of tested metabolites. Specific examples include two subunits of a predicted ABC transporter encoded by the genes SO1043 and SO1044 required for the utilization of citrulline and a predicted histidase encoded by the gene SO3057 required for the utilization of ergothioneine by S. oneidensis. In vitro assays with purified proteins showed substrate specificity of SO3057 toward ergothioneine and histidine betaine in contrast to substrate specificity of a paralogous histidase SO0098 toward histidine. This generally applicable, high-throughput workflow has the potential both to discover novel metabolic capabilities of microorganisms and to identify the corresponding genes.