Differences in the genomic makeup of microbial strains can profoundly alter their behavior, ecological roles, and consequences for human health. Traditionally, a species' relative abundance has been used to identify associations between the microbiome and disease. However, this approach overlooks intra-species genetic variation and is susceptible to spurious correlations arising from the compositional nature of abundance data. Recent k-mer based algorithms now enable rapid and accurate estimation of strain-level Average Nucleotide Identity (containment ANI) between metagenomic samples and reference databases. Despite its value as an orthogonal metric for strain-level microbiome analysis, methods for conducting such association studies remain limited. To address this, we developed StrainSpy, an algorithm that links containment ANI to phenotypes of interest across a range of study designs. Using extensive simulations, we demonstrate that StrainSpy is more accurate than alternative approaches. Re-analysis of a study examining gut microbiota recovery in 12 healthy adults following antibiotic exposure revealed novel strain-level associations, including a reduction in intraspecies diversity despite species persistence. Notably, using StrainSpy, we found that certain previously reported associations were confounded by microbial load. We further applied StrainSpy to consider a pooled analysis of 3,414 stool metagenomes from 17 cohorts to identify strain-level associations with colorectal cancer. In addition to uncovering both known and novel associations, we show that a machine learning model incorporating containment ANI and strain presence–absence achieves comparable accuracy in distinguishing colorectal cancer patients from healthy individuals as models based on abundance data.