Probiotics are live microorganisms which confer health benefits to the host, and may be isolated from several sources, such as vegetable foodstuffs. Sauerkraut is a cabbage product resulting from fermentation by a lactic acid bacteria microbial succession, and is a potential source for probiotics. The aim of the present study was the isolation and characterization of probiotic microorganisms from sauerkraut fermentations. Four distinct fermentations were performed, from which lactic acid bacteria were recovered. Overall, 114 isolates were obtained, phenotypically and genotypically characterized, identified to the genus level and evaluated regarding safety and probiotic potential. Representative bacteria were selected for further analysis, 52% being Lactobacillus spp. and 33% belonging to Leuconostoc spp. genus. One isolate revealed to be β-hemolytic, 42% possessed potentially mobile antimicrobial resistance, 88% were resistant to bile and 20% to low pH. The six most promising candidates were further characterized and presented antimicrobial activity against Listeria monocytogenes, three being resistant to lower pH values. Thus, global analysis of data gathered during this study highlighted the identification of three Lactobacillus strains with putative probiotic potential, suggesting the applicability of sauerkraut fermentations as a source for probiotic isolation. Due to their origin these strains should be suited for future application in the food industry, namely vegetable products such as sauerkraut itself.