The aims of this study were to investigate the diversity of lactic acid bacteria (LAB) isolated from traditional Mongolian dairy products, and to estimate the probiotic potential of the isolated strains. We collected 66 samples of the traditional Mongolian dairy products tarag (n = 45), airag (n = 7), aaruul (n = 8), byasulag (n = 1) and eezgii (n = 5), from which 543 LAB strains were isolated and identified based on 16S ribosomal DNA sequence. The predominant species of those products were Lactobacillus (L.) delbrueckii ssp. bulgaricus, L. helveticus, L. fermentum, L. delbrueckii ssp. lactis and Lactococcus lactis ssp. lactis. However, we could not detect any LAB strains from eezgii. All LAB isolates were screened for tolerance to low pH and to bile acid, gas production from glucose, and adherence to Caco-2 cells. In vitro, we found 10 strains possess probiotic properties, and almost identified them as L. plantarum or L. paracasei subspecies, based on 16S ribosomal DNA and carbohydrate fermentation pattern. These strains were differentiated from each other individually by randomly amplified polymorphic DNA analysis. Additionally, it was notable that 6/10 strains were isolated from camel milk tarag from the Dornogovi province.