Loss of diversity in the gut microbiome can persist for extended periods after antibiotic treatment, impacting microbiome function, antimicrobial resistance and probably host health. Despite widespread antibiotic use, our understanding of the species and metabolic functions contributing to gut microbiome recovery is limited. Using data from 4 discovery cohorts in 3 continents comprising >500 microbiome profiles from 117 individuals, we identified 21 bacterial species exhibiting robust association with ecological recovery post antibiotic therapy. Functional and growth-rate analysis showed that recovery is supported by enrichment in specific carbohydrate-degradation and energy-production pathways. Association rule mining on 782 microbiome profiles from the MEDUSA database enabled reconstruction of the gut microbial ‘food web’, identifying many recovery-associated bacteria as keystone species, with the ability to use host- and diet-derived energy sources, and support repopulation of other gut species. Experiments in a mouse model recapitulated the ability of recovery-associated bacteria (Bacteroides thetaiotaomicron and Bifidobacterium adolescentis) to promote recovery with synergistic effects, providing a boost of two orders of magnitude to microbial abundance in early time points and faster maturation of microbial diversity. The identification of specific species and metabolic functions promoting recovery opens up opportunities for rationally determining pre- and probiotic formulations offering protection from long-term consequences of frequent antibiotic usage.