Bacterial adhesion to host cells is the most important probiotic character. However, the adhesion of probiotic should not affect the viability of the host cells. In this study, Lactobacillus plantarum strain L8, Lactobacillus plantarum strain L20 and Lactobacillus pentosus strain S1 were tested for their cytotoxic effects through MTT assay and their ability to adhere and colonize on HT-29 and CCD-18Co intestinal cells as detected microscopically using light microscopy and Scanning Electron Microscopy (SEM). No cytotoxicity effects were observed on both intestinal cells following 24 h treatment with all Lactobacillus strains. Additionally, all strains demonstrated strong adhesive activity where more than 100 bacteria adhered to both intestinal cells although differences in the adhesion scores observed among different strains. The adhesion as observed via SEM showed an autoagreggative pattern and adhered as clusters on the surface of both intestinal cells. In conclusion, all three Lactobacillus strains are non-cytotoxic to both cells with strong adhesion ability on intestinal cells and this study also proved that Malaysian fermented fish are good source of probiotic bacteria.