Algerian fermented foods represent a precious source of indigenous yeasts with potentially probiotic properties, which can serve as regional, functional starter cultures. The aim of the present research is to isolate and genetically identify strains obtained from traditional fermented foods and investigate their probiotic properties and safety aspects in vitro. The molecular identification revealed fifteen S. cerevisiae strains obtained from sourdoughs and marinated peppers samples. All tested strains showed the ability to grow at 37 °C and to survive well at 0.3% (w/v) bile salts with high resistance to pH 2.5. The auto-aggregation rates of tested strains reached 93.90% after 24 h of incubation, while seven of fifteen strains showed high hydrophobicity values in xylene (44.60–58.90%), indicating their ability to survive and to adhere to the host intestinal mucosa. All S. cerevisiae isolates showed a good antioxidant activity and exhibited varying levels of antibacterial activity, but not against Listeria innocua. A lack of hemolysis, gelatinase, protease and phospholipase was recorded for all tested strains, while a strong phytase activity was observed in these strains, which may enhance mineral availability and reduce antinutritional effects of plant-based food. Based on these results, five S. cerevisiae strains showed promising probiotic properties and safety aspects, which can be used as potential probiotic strains in functional food industries and/or in the medical field.