Alzheimer’s disease (AD) pathology is thought to progress from normal cognition through preclinical disease and ultimately to symptomatic AD with cognitive impairment. Recent work suggests that the gut microbiome of symptomatic patients with AD has an altered taxonomic composition compared with that of healthy, cognitively normal control individuals. However, knowledge about changes in the gut microbiome before the onset of symptomatic AD is limited. In this cross-sectional study that accounted for clinical covariates and dietary intake, we compared the taxonomic composition and gut microbial function in a cohort of 164 cognitively normal individuals, 49 of whom showed biomarker evidence of early preclinical AD. Gut microbial taxonomic profiles of individuals with preclinical AD were distinct from those of individuals without evidence of preclinical AD. The change in gut microbiome composition correlated with β-amyloid (Aβ) and tau pathological biomarkers but not with biomarkers of neurodegeneration, suggesting that the gut microbiome may change early in the disease process. We identified specific gut bacterial taxa associated with preclinical AD. Inclusion of these microbiome features improved the accuracy, sensitivity, and specificity of machine learning classifiers for predicting preclinical AD status when tested on a subset of the cohort (65 of the 164 participants). Gut microbiome correlates of preclinical AD neuropathology may improve our understanding of AD etiology and may help to identify gut-derived markers of AD risk.