Stinky tofu is a kind of fermented tofu with a strong odor. Although stinky tofu is a very popular snack in the Asian region, the community of microbes, and especially lactic acid bacteria (LAB), indigenous to the fermented brine from which it is made remains poorly described. We examined 168 isolates obtained from the original fermented brine (brine A) and two brines in which the hard tofu (brine B) and soft tofu (brine C) had been soaked. Through random amplified polymorphic DNA (RAPD) analysis for typing and 16S rDNA sequencing, 136 representative strains were identified as belonging to 7 genera and 32 species: Enterococcus (2 species), Lactobacillus (14 species), Lactococcus (3 species), Leuconostoc (6 species), Pediococcus (1 species), Streptococcus (2 species), and Weissella (4 species). The LAB composition of brine A was the most diverse: 19 different species were isolated, and 9 of them were classified as Lactobacillus species. The 16S rDNA sequences of 9 strains (6 from brine A and 3 from brine C) showed low values of similarity (below 98%) with currently known species by analysis using the FASTA software. Thus, a wide variety of LAB strains were associated with the fermentation of stinky tofu brines.