Background/Objectives: Dysgeusia contributes to malnutrition and worsens the quality of life of patients with cancer. Despite the different strategies, there is no effective treatment for patients suffering from taste disorders provided by the pharmaceutical industry. Therefore, we developed a novel strategy for reducing side effects in cancer patients by providing a novel food supplement with the taste-modifying glycoprotein miraculin, which is approved by the European Union, as an adjuvant to medical–nutritional therapy. Methods: A pilot randomized, parallel, triple-blind, and placebo-controlled intervention clinical trial was carried out in which 31 malnourished patients with cancer and dysgeusia receiving antineoplastic treatment were randomized into three arms—standard dose of dried miracle berries (DMBs) (150 mg DMB/tablet), high dose of DMBs (300 mg DMB/tablet), or placebo (300 mg freeze-dried strawberry)—for three months. Patients consumed a DMB or placebo tablet before each main meal (breakfast, lunch, and dinner). Using stool samples from patients with cancer, we analyzed the intestinal microbiome via nanopore methodology. Results: We detected differences in the relative abundances of genera Phocaeicola and Escherichia depending on the treatment. Nevertheless, only the Solibaculum genus was more abundant in the standard-dose DMB group after 3 months. At the species level, Bacteroides sp. PHL 2737 presented a relatively low abundance in both DMB groups, whereas Vescimonas coprocola presented a relatively high abundance in both treatment groups after 3 months. Furthermore, a standard dose of DMB was positively associated with TNF-α levels and Lachnoclostridium and Mediterraneibacter abundances, and a high dose of DMB was negatively associated with TNF-α levels and the relative abundance of Phocaeicola. Following the administration of a high dose of DMB, a positive correlation was observed between erythrocyte polyunsaturated fatty acids and the presence of Lachnoclostridium and Roseburia. Additionally, a positive association was identified between Phocaeicola and the acetic acid concentration of feces. There was a negative association between the relative abundance of Phocaeicola and taste perception in the high-dose DMB group. Conclusions: The combination of DMB intake with nutritional treatment and individualized dietary guidance results in positive changes in the intestinal microbiome of patients with cancer and dysgeusia. Changes observed in the intestinal microbiome might contribute to maintaining an appropriate immune response in cancer patients. As the current pilot study included a limited number of participants, further clinical trials on a larger group of patients are needed to draw robust findings.