Gut microbiome (GM) and its either pro-tumorigenic or anti-tumorigenic role is intriguing and constitutes an evolving landscape in translational oncology. It has been suggested that these microorganisms may be involved in carcinogenesis, cancer treatment response and resistance, as well as predisposition to adverse effects. In melanoma patients, one of the most immunogenic cancers, immune checkpoint inhibitors (ICI) and MAPK-targeted therapy—BRAF/MEK inhibitors—have revolutionized prognosis, and the study of the microbiome as a modulating factor is thus appealing. Although BRAF/MEK inhibitors constitute one of the main backbones of treatment in melanoma, little is known about their impact on GM and how this might correlate with immune re-induction. On the contrary, ICI and their relationship to GM has become an interesting field of research due to the already-known impact of immunotherapy in modulating the immune system. Immune reprogramming in the tumor microenvironment has been established as one of the main targets of microbiome, since it can induce immunosuppressive phenotypes, promote inflammatory responses or conduct anti-tumor responses. As a result, ongoing clinical trials are evaluating the role of fecal microbiota transplant (FMT), as well as the impact of using dietary supplements, antibiotics and probiotics in the prediction of response to therapy. In this review, we provide an overview of GM’s link to cancer, its relationship with the immune system and how this may impact response to treatments in melanoma patients. We also discuss insights about novel therapeutic approaches including FMT, changes in diet and use of probiotics, prebiotics and symbiotics. Finally, we hypothesize on the possible pathways through which GM may impact anti-tumor efficacy in melanoma patients treated with targeted therapy, an appealing subject of which little is known.