Disruption of the gut microbiome composition is associated with many metabolic, inflammatory, and infectious diseases in humans. Accurately profiling microbiomes at the strain level is important for gaining a clear understanding of the microbiome’s role in disease. However, the existing tools can’t reliably classify microbes at strain resolution, making it difficult to detect composition changes. A new bioinformatic tool, SameStr, addresses this difficulty by identifying strains that are shared between metagenomes according to the similarity of single-nucleotide variants (SNVs) in certain species-specific marker genes. In validation studies, SameStr was more sensitive than other tools in identifying shared strains among mock populations, while remaining robust against false-positives. SameStr was also able to identify persistent strains in the fecal microbiomes of healthy adult humans and to detect strains that successfully engrafted in patients with recurrent Clostridioides difficile infection after fecal microbiota transfer. Further analyses with SameStr revealed a set of core microbes that persist in the healthy human gut. Although SameStr can’t quantify strains, its ability to detect shared strains makes it useful for metagenome comparisons, providing a new way to investigate how the microbiome is altered under disease conditions.