IgA, the most highly produced human antibody, is continually secreted into the gut to shape the intestinal microbiota. Methodological limitations have critically hindered defining which microbial strains are targeted by IgA and why. Here, we develop a new technique, Metagenomic Immunoglobulin Sequencing (MIG-Seq), and use it to determine IgA coating levels for thousands of gut microbiome strains in healthy humans. We find that microbes associated with both health and disease have higher levels of coating, and that microbial genes are highly predictive of IgA binding levels, with mucus degradation genes especially correlated with high binding. We find a significant reduction in replication rates among microbes bound by IgA, and demonstrate that IgA binding is more correlated with host immune status than traditional microbial abundance measures. This study introduces a powerful technique for assessing strain-level IgA binding in human stool, paving the way for deeper understanding of IgA-based host microbe interactions.