Studies in mice and humans have revealed intriguing associations between host genetics and the microbiome. Here we report a 16S rRNA-based analysis of the gut microbiome in 1,126 twin pairs, a subset of which was previously reported. Tripling the sample narrowed the confidence intervals around heritability estimates and uncovered additional heritable taxa, some of which are validated in other studies. Repeat sampling of subjects showed heritable taxa to be temporally stable. A candidate gene approach uncovered associations between heritable taxa and genes related to diet, metabolism, and olfaction. We replicate an association between Bifidobacterium and the lactase (LCT) gene locus and identify an association between the host gene ALDH1L1 and the bacteria SHA-98, suggesting a link between formate production and blood pressure. Additional genes detected are involved in barrier defense and self/non-self recognition. Our results indicate that diet-sensing, metabolism, and immune defense are important drivers of human-microbiome co-evolution.