The gut microbiome (GMB) has been associated with outcomes of immune checkpoint blockade therapy in melanoma, but there is limited consensus on the specific taxa involved, particularly across different geographic regions. We analyzed pre-treatment stool samples from 674 melanoma patients participating in a phase-III trial of adjuvant nivolumab plus ipilimumab versus nivolumab, across three continents and five regions. Longitudinal analysis revealed that GMB was largely unchanged following treatment, offering promise for lasting GMB-based interventions. In region-specific and cross-region meta-analyses, we identified pre-treatment taxonomic markers associated with recurrence, including Eubacterium, Ruminococcus, Firmicutes, and Clostridium. Recurrence prediction by these markers was best achieved across regions by matching participants on GMB compositional similarity between the intra-regional discovery and external validation sets. AUCs for prediction ranged from 0.83-0.94 (depending on the initial discovery region) for patients closely matched on GMB composition (e.g., JSD ≤0.11). This evidence indicates that taxonomic markers for prediction of recurrence are generalizable across regions, for individuals of similar GMB composition.