In this work, a study regarding the encapsulation of the probiotic strain Bifidobacterium animalis subsp. lactis (BB-12) through emulsification followed by external gelation was performed. For this purpose, a variety of alginate-based blends, composed of conventional and novel materials, were used. The results demonstrated that alginate beads incorporating 1% carrageenan or 2% nanocrystalline cellulose provided great protection during refrigerated storage (50.3% and 51.1%, respectively), as well as in vitro simulation of the gastroinestinal tract (38.7 and 42.0%, respectively). The incorporation of glycerol into the formulation of the beads was proved successful for the protection of the BB-12 cells during frozen storage, increasing significantly their viability compared to the plain alginate beads (survival rate of 57.1% after 30 days at -18oC, instead of non-viable cells). Beads made of milk, alginate 1%, glucose 5% and inulin provided the best results at all cases. The microstructure of beads was assessed through SEM analysis.