Multiple clinical trials targeting the gut microbiome are being conducted to optimize treatment outcomes for immune checkpoint blockade (ICB). To improve the success of these interventions, understanding gut microbiome dynamics during ICB is urgently needed. Through longitudinal shotgun metagenomics profiling in 175 patients treated with ICB for advanced melanoma, we show that microbial species-level genome bins (SGBs; an improved species-delineation) and pathways exhibit contrasting patterns from baseline in patients achieving progression-free survival (PFS) of 12 months or longer (PFS≥12) vs. patients with PFS shorter than 12 months (PFS<12). Out of 99 SGBs that were able to discriminate between patients with PFS ≥ or < 12 months, 20 SGBs were differentially abundant only at baseline, while 42 were differentially abundant only after treatment initiation. Butyrate producers were enriched in patients with PFS≥12 months at baseline but also during most of the study period. Patients with a PFS<12 months exhibited an increase in Clostridium spiroforme, Blautia, Ruminococcus torques and Turicibacter sanguinis SGBs only after the start of ICB. We identify five SGBs that had consistently higher abundances in patients with PFS ≥12 months (Agathobaculum butyriciproducens [SGB14993 group], Intestinibacter bartlettii [SGB6140], Dorea sp AF24 7LB [SGB4571], Lactobacillus gasseri [SGB7038 group] and Lacrimispora celerecrescens [SGB4868]), and four that had consistently higher abundances in patients with PFS<12 months (Ruthenibacterium lactatiformans [SGB15271], Prevotella copri clade A [SGB1626], Ruminococcaceae unclassified [SGB15265 group], Bacteroidetes unclassified [SGB1957]). We present a log-ratio of these SGBs that can discriminate between patients achieving PFS12 and patients with a PFS<12 months and is associated with overall survival. A number of species considered immunogenic, including Streptococcus and Parabacteroides strains, showed increasing abundances in patients with ≥ PFS12 during ICB. We identify another log-ratio that predicts development of ICB-induced colitis. While patients with ≥ PFS12 resistant to colitis exhibited higher abundances of several Faecalibacterium prausnitzii SGBs, Akkermansia muciniphila (SGB9226) was enriched in patients with ≥ PFS12 developing colitis. Regression models that included higher-order interactions revealed different microbial dynamics for different treatment scenarios including the type of ICB regimen, development of irAEs and concomitant medication use. Longitudinal dynamics of the gut microbiome and their integration with other host factors are critical for guiding rational microbiome-targeted therapies aimed at enhancing ICB efficacy.