Largely due to challenges cultivating microbes under laboratory conditions, the genome sequence of many species in the human gut microbiome remains unknown. To address this problem, we reconstructed 60,664 prokaryotic draft genomes from 3,810 faecal metagenomes from geographically and phenotypically diverse human subjects. These genomes provide reference points for 2,058 previously unknown species-level operational taxonomic units (OTUs), representing a 50% increase in the phylogenetic diversity of sequenced gut bacteria. On average, new OTUs comprise 33% of richness and 28% of species abundance per individual and are enriched in humans from rural populations. A meta-analysis of clinical gut microbiome studies pinpointed numerous disease associations for new OTUs, which have the potential to improve predictive models. Finally, our analysis revealed that uncultured gut species have undergone genome reduction with loss of certain biosynthetic pathways, which may offer clues for improving cultivation strategies in the future.