Several arguments have been made to substantiate the need for natural antimicrobials for the food industry. With blueberry extracts, the most compelling are both their healthy connotation and the possibility of obtaining a multipurpose solution that can be an antioxidant, colorant, and antimicrobial. From an antimicrobial perspective, as blueberry/anthocyanin-rich extracts have been associated with a capacity to inhibit harmful bacteria while causing little to no inhibition on potential probiotic microorganisms, the study of potential benefits that come from synergies between the extract and probiotics may be of particular interest. Therefore, the present work aimed to evaluate the effect of an anthocyanin-rich extract on the adhesion of five different probiotics as well as their effect on the probiotics’ capacity to compete with or block pathogen adhesion to a mucin/BSA-treated surface. The results showed that, despite some loss of probiotic adhesion, the combined presence of extract and probiotic is more effective in reducing the overall amount of adhered viable pathogen cells than the PROBIOTIC alone, regardless of the probiotic/pathogen system considered. Furthermore, in some instances, the combination of the extract with Bifidobacterium animalis Bo allowed for almost complete inhibition of pathogen adhesion.