Pre-clinical mouse models suggest that the gut microbiome modulates tumor response to checkpoint blockade immunotherapy; however, this has not been well-characterized in human cancer patients. Here we examined the oral and gut microbiome of melanoma patients undergoing anti-PD-1 immunotherapy (n=112). Significant differences were observed in the diversity and composition of the patient gut microbiome of responders (R) versus non-responders (NR). Analysis of patient fecal microbiome samples (n=43, 30R, 13NR) showed significantly higher alpha diversity (p<0.01) and relative abundance of Ruminococcaceae bacteria (p<0.01) in responding patients. Metagenomic studies revealed functional differences in gut bacteria in R including enrichment of anabolic pathways. Immune profiling suggested enhanced systemic and anti-tumor immunity in responding patients with a favorable gut microbiome, as well as in germ-free mice receiving fecal transplants from responding patients. Together, these data have important implications for the treatment of melanoma patients with immune checkpoint inhibitors.