Background: Microencapsulation is a technique which improves the survival and viability of probiotics. We demonstrate encapsulation of five potential probiotic yeasts with alginate and gum as encapsulation matrices to improve their gastrointestinal transit. Methods: Gum extracted from various cereals viz. rice, oats, barley, finger millet and pearl millet along with alginate have been used to encapsulate five potential probiotic yeasts. Screening was carried out by measuring swelling index, encapsulation efficiency and nutritional value of microcapsules encapsulated with alginate and gum. The concentration of OBG, sodium alginate and inoculum dosage of probiotic yeasts was optimized using response surface methodology (RSM). Efficiency of alginate OBG microcapsules with or without coating materials viz. whey protein and chitosan also tested. The mucoadhesion ability and storage stability of alginate OBG microcapsules with coating materials were tested. Results: Highest encapsulation efficiency of probiotic yeasts was noted using oats bran gum (OBG) microcapsules along with alginate in all the five probiotic yeasts. Notably whey protein coated microcapsules showed maximum GIT tolerance (95{\%}) and mucoadhesion (90{\%}) for L. starkeyi VIT-MN03. The minimum loss of viability was observed in L. starkeyi VITMN03 microcapsules on 60th day of storage. Conclusions: This is the first report on optimization and survival of microencapsulated probiotic yeasts under simulated GIT conditions using natural gum and alginate as encapsulation matrices and whey protein as coating material.