BACKGROUND While human gut microbiomes vary significantly in taxonomic composition, biological pathway abundance is surprisingly invariable across hosts. We hypothesized that healthy microbiomes appear functionally redundant due to factors that obscure differences in gene abundance between individuals. RESULTS To account for these biases, we developed a powerful test of gene variability called CCoDA, which is applicable to shotgun metagenomes from any environment and can integrate data from multiple studies. Our analysis of healthy human fecal metagenomes from three separate cohorts revealed thousands of genes whose abundance differs significantly and consistently between people, including glycolytic enzymes, lipopolysaccharide biosynthetic genes, and secretion systems. Even housekeeping pathways contain a mix of variable and invariable genes, though most highly conserved genes are significantly invariable. Variable genes tend to be associated with Proteobacteria, as opposed to taxa used to define enterotypes or the dominant phyla Bacteroidetes and Firmicutes. CONCLUSIONS These results establish limits on functional redundancy and predict specific genes and taxa that may explain physiological differences between gut microbiomes.