In this study, Streptococcus macedonicus (S. macedonicus) strains were identified from Algerian traditional fermented milks (Lben and Rayeb). Important prerequisites of probiotic interest such as acidity, bile salts tolerance, and adhesion ability to epithelial cells were investigated. A combination of phenotypic (ability to grow on Bile Esculin Azide medium, BEA; on high salt content medium NaCl 6.5%; on alkaline medium pH 9.6) and genotypic approaches (16S rRNA, ITS genes sequencing and MLST technique) allowed to identify four genetically distinct strains of S. macedonicus. These four strains and two references, Streptococcus thermophilus LMD-9 and Lactobacillus rhamnosus GG (LGG), were tested for their capacity to survive at low pH values, and at different concentrations of an equimolar bile salts mixture (BSM). Two different cell lines, Caco-2 TC7 and HT29-MTX, were used for the adhesion study. The results show that S. macedonicus strains selected constitute a distinct genetic entity from the Greek strain S. macedonicus ACA-DC-198. They were able to survive up to pH 3 and could tolerate high concentrations of bile salts (10 mM), unlike LMD-9 and LGG strains. Our strains also display in vitro adhesion similar to the LGG strain on Caco-2 TC7 and higher adhesion than the LMD-9 strain to Caco-2 TC7 and HT29-MTX cell models. This first characterization allows considering S. macedonicus as a potential candidate for possible probiotic effects that need to be investigated.