We aimed to develop an innovative synbiotic formulation for use in reducing dysbiosis, uremic toxins (e.g., p-cresol and indoxyl sulfate), and, consequently, the pathognomonic features of patients with chronic kidney disease (CKD). Twenty-five probiotic strains, belonging to lactobacilli and Bifidobacterium, were tested for their ability to grow in co-culture with different vegetable (pomegranate, tomato, and grapes) sources of antioxidants and prebiotics (inulin, fructo-oligosaccharides, and β-glucans). Probiotics were selected based on the acidification rates and viable cell counts. Inulin and fructo-oligosaccharides reported the best prebiotic activity, while a pomegranate seed extract was initially chosen as antioxidant source. The investigation was also conducted in fecal batches from healthy and CKD subjects, on which metabolomic analyses (profiling volatile organic compounds and total free amino acids) were conducted. Two out of twenty-five probiotics were finally selected. After the stability tests, the selective innovative synbiotic formulation (named NatuREN G) comprised Bifidobacterium animalis BLC1, Lacticaseibacillus casei LC4P1, fructo-oligosaccharides, inulin, quercetin, resveratrol, and proanthocyanidins. Finally, NatuREN G was evaluated on fecal batches collected from CKD in which modified the viable cell densities of some cultivable bacterial patterns, increased the concentration of acetic acid and decane, while reduced the concentration of nonanoic acid, dimethyl trisulfide, and indoxyl sulfate.