Significance Recent surveys of the microbial communities living on and in the human body—the human microbiome—have revealed strong variation in community membership between individuals. Some of this variation is stable over time, leading to speculation that individuals might possess unique microbial “fingerprints” that distinguish them from the population. We rigorously evaluated this idea by combining concepts from microbial ecology and computer science. Our results demonstrated that individuals could be uniquely identified among populations of 100s based on their microbiomes alone. In the case of the gut microbiome, >80% of individuals could still be uniquely identified up to a year later—a result that raises potential privacy concerns for subjects enrolled in human microbiome research projects. Community composition within the human microbiome varies across individuals, but it remains unknown if this variation is sufficient to uniquely identify individuals within large populations or stable enough to identify them over time. We investigated this by developing a hitting set-based coding algorithm and applying it to the Human Microbiome Project population. Our approach defined body site-specific metagenomic codes: sets of microbial taxa or genes prioritized to uniquely and stably identify individuals. Codes capturing strain variation in clade-specific marker genes were able to distinguish among 100s of individuals at an initial sampling time point. In comparisons with follow-up samples collected 30–300 d later, ∼30% of individuals could still be uniquely pinpointed using metagenomic codes from a typical body site; coincidental (false positive) matches were rare. Codes based on the gut microbiome were exceptionally stable and pinpointed >80% of individuals. The failure of a code to match its owner at a later time point was largely explained by the loss of specific microbial strains (at current limits of detection) and was only weakly associated with the length of the sampling interval. In addition to highlighting patterns of temporal variation in the ecology of the human microbiome, this work demonstrates the feasibility of microbiome-based identifiability—a result with important ethical implications for microbiome study design. The datasets and code used in this work are available for download from huttenhower.sph.harvard.edu/idability .