This work reports on the first described aerotolerant Bifidobacterium bifidum strain, Bifidobacterium bifidum IPLA60003, which has the ability to form colonies on the surface of agar plates under aerobic conditions, a weird phenotype that to our knowledge has never been observed in B. bifidum. The strain IPLA60003 was generated after random UV mutagenesis from an intestinal isolate. It incorporates 26 single nucleotide polymorphisms that activate the expression of native oxidative-defense mechanisms such as the alkyl hydroxyperoxide reductase, the glycolytic pathway and several genes coding for enzymes involved in redox reactions. In the present work, we discuss the molecular mechanisms underlying the aerotolerance phenotype of B. bifidum IPLA60003, which will open new strategies for the selection and inclusion of probiotic gut strains and next generation probiotics into functional foods.