The gut microbiome modulates immune and metabolic health. Human microbiome data are biased toward industrialized populations, limiting our understanding of non-industrialized microbiomes. Here, we performed ultra-deep metagenomic sequencing on 351 fecal samples from the Hadza hunter-gatherers of Tanzania and comparative populations in Nepal and California. We recovered 91,662 genomes of bacteria, archaea, bacteriophages, and eukaryotes, 44% of which are absent from existing unified datasets. We identified 124 gut-resident species vanishing in industrialized populations and highlighted distinct aspects of the Hadza gut microbiome related to in situ replication rates, signatures of selection, and strain sharing. Industrialized gut microbes were found to be enriched in genes associated with oxidative stress, possibly a result of microbiome adaptation to inflammatory processes. This unparalleled view of the Hadza gut microbiome provides a valuable resource, expands our understanding of microbes capable of colonizing the human gut, and clarifies the extensive perturbation induced by the industrialized lifestyle. Display omitted •The largest set of gut microbiome sequencing data from a hunter-gatherer population•Assembly of thousands of novel human gut bacteria, archaea, eukaryotes, and phages•Identification of distinct functions in lifestyle-associated VANISH and BloSSUM taxa•Extensive non-kin strain sharing associated with a unique Hadza social structure Ultra-high-depth sequencing of the gut microbiome of hunter-gatherers enables comparative analysis with industrialized microbiomes and provides a unique resource of the non-industrialized microbiome and an interrogation of the ecology and evolution of bacterial symbionts.