Background: An unbalanced skin microbiota due to an increase in pathogenic vs. commensal bacteria can be efficiently tackled by using prebiotics. The aim of this work was to identify novel prebiotic combinations by exerting species-specific action between S. aureus and S. epidermidis strains. Methods: First, the antimicrobial/antibiofilm effect of Xylitol-XYL and Galacto-OligoSaccharides–GOS combined with each other at different concentrations (1, 2.5, 5%) against S. aureus and S. epidermidis clinical strains was evaluated in time. Second, the most species-specific concentration was used to combine XYL with Fructo-OligoSaccharides–FOS, IsoMalto-Oligosaccharides–IMO, ArabinoGaLactan–LAG, inulin, dextran. Experiments were performed by OD600 detection, biomass quantification and LIVE/DEAD staining. Results: 1% XYL + 1% GOS showed the best species-specific action with an immediate antibacterial/antibiofilm action against S. aureus strains (up to 34.54% ± 5.35/64.68% ± 4.77) without a relevant effect on S. epidermidis. Among the other prebiotic formulations, 1% XYL plus 1% FOS (up to 49.17% ± 21.46/37.59% ± 6.34) or 1% IMO (up to 41.28% ± 4.88/36.70% ± 10.03) or 1% LAG (up to 38.21% ± 5.31/83.06% ± 5.11) showed antimicrobial/antibiofilm effects similar to 1% XYL+1% GOS. For all tested formulations, a prevalent bacteriostatic effect in the planktonic phase and a general reduction of S. aureus biofilm formation without loss of viability were recorded. Conclusion: The combinations of 1% XYL with 1% GOS or 1% FOS or 1% IMO or 1% LAG may help to control the balance of skin microbiota, representing good candidates for topic formulations.