From 16 samples of traditional fermented koumiss collected in Inner Mongolia Autonomous Region of China, forty-eight lactobacilli strains were isolated and phenotypically characterized by their abilities to ferment different carbohydrates and by additional biochemical tests. The dominant lactobacilli species were identified as L. casei (17 strains), L. helveticus (10 strains) and L. plantarum (8 strains), with a lower frequency of isolation for L. coryniformis subsp. coryniformis (5 strains), L. paracasei (3 strains), L. kefiranofaciens (2 strains), L. curvatus (1 strain), L. fermentum (1 strain) and W. kandleri (1 strain). The pH values of all these samples were ranging from 3.37 to 3.94. In isolates, L. casei Zhang, L. helveticus ZL12-1, and L. plantarum BX6-6 were selected as potentially probiotic strains through the preliminary tests including resistance to low acid, abilities to grow in MRS with bile salts, antimicrobial activities and the viabilities during prolonged cold storage in fermented milk. Moreover 16S rDNA was conducted to confirm the identification.