Immune checkpoint inhibitors (ICI) targeting the PD-1/PD-L1 axis induce sustained clinical responses in a sizeable minority of cancer patients. Here, we show that primary resistance to ICI can be due to abnormal gut microbiome composition. Antibiotics (ATB) inhibited the clinical benefit of ICI in patients with advanced cancer. Fecal microbiota transplantation (FMT) from cancer patients who responded to ICI (but not from non-responding patients) into germ-free or ATB-treated mice ameliorated the antitumor effects of PD-1 blockade. Metagenomics of patient stools at diagnosis revealed correlations between clinical responses to ICI and the relative abundance of Akkermansia muciniphila. Oral supplementation with A. muciniphila post-FMT with non-responder feces restored the efficacy of PD-1 blockade in an IL-12-dependent manner, by increasing the recruitment of CCR9+CXCR3+CD4+ T lymphocytes into tumor beds.