Increasing evidence suggests that a brain-gut-microbiome axis exists, which has the potential to play a major role in modulating behaviour. However, the role of this axis in cognition remains relatively unexplored. Probiotics, which are commensal bacteria offering potential health benefit, have been shown to decrease anxiety, depression and visceral pain-related behaviours. In this study, we investigate the potential of two Bifidobacteria strains to modulate cognitive processes and visceral pain sensitivity. Adult male BALB/c mice were fed daily for 11 weeks with B. longum 1714, B. breve 1205 or vehicle treatment. Starting at week 4, animals were behaviourally assessed in a battery of tests relevant to different aspects of cognition, as well as locomotor activity and visceral pain. In the object recognition test, B. longum 1714-fed mice discriminated between the two objects faster than all other groups and B. breve 1205-fed mice discriminated faster than vehicle animals. In the Barnes maze, B. longum 1714-treated mice made fewer errors than other groups, suggesting a better learning. In the fear conditioning, B. longum 1714-treated group also showed better learning and memory, yet presenting the same extinction learning profile as controls. None of the treatments affected visceral sensitivity. Altogether, these data suggest that B. longum 1714 had a positive impact on cognition and also that the effects of individual Bifidobacteria strains do not generalise across the species. Clinical validation of the effects of probiotics on cognition is now warranted.