Sixty-seven (67) lactic acid bacteria (LAB) isolates belonging to Lactobacillus genus were isolated from human feces and tested for their auto-aggregation and cell surface hydrophobicity in order to establish their adhesion capabilities, a prerequisite for probiotic selection. Strains with the upmost auto-aggregation and cell surface hydrophobicity scores were identified by MALDI-TOF spectrometry and 16S rDNA sequencing as Lactobacillus plantarum (p25lb1 and p98lb1) and Lactobacillus salivarius (p85lb1 and p104lb1). These strains were also able to adhere to human epithelial colorectal adenocarcinoma Caco-2 cells, with percentages ranging from 4.68 to 9.59%. They displayed good survival under conditions mimicking the gastrointestinal environment and remarkably impeded adhesion and invasion of human Caco-2 by Listeria monocytogenes and Enteropathogenic Escherichia coli. It should also be noted that Lb. plantarum p98lb1 was able to reduce in vitro cholesterol concentration by about 32%, offering an additional health attribute.