Lactic acid bacteria (LAB) are used in the food industry for fermentation and preservation. Additionally, certain LAB provide beneficial activity to animal or human health. This study assessed five LAB strains, including Latilactobacillus sakei A60 and 4-44, Lactiplantibacillus paraplantarum D02, and Latilactobacillus curvatus 4-36 and 4-43, as new fermentation starters with both antimicrobial and probiotic activities. The strains showed growth at 5°C and over 6% (w/v) NaCl, which are the conditions expected in food processing and storage. Their antimicrobial activity against eight microorganisms commonly associated with food spoilage was examined at various growth temperatures. They exhibited antimicrobial activity at 25°C, 30°C, and 37°C and showed higher activity at 25°C than at 30°C and 37°C. All strains except D02 showed antimicrobial activity at 5°C. In terms of probiotic activities, all strains showed high or comparable mucin-binding activity, and strains A60 and 4-43 exhibited relatively higher tolerance to bile than that of Lacticaseibacillus rhamnosus GG, a potential probiotic bacterium. Strains A60, D02, and A-36 showed increased mucin adhesion via culturing with 6% (w/v) NaCl. These strains would be useful not only in food processing and storage but also in health-related applications, as they colonize the intestine and suppress the growth of pathogenic bacteria.