Leuconostoc mesenteroides strains were a type of epiphytic bacterium widely used in fermented foods and products in the biochemical and pharmaceutical industries but data on its presence in foods from Qinghai-Tibet Plateau in China was scarce. In this study, molecular analysis based on multilocus sequence typing (MLST) with eight housekeeping genes (pyrG, groeL, rpoB, recA, uvrC, murC, carB, and pheS) was carried out on 45 L. mesenteroides strains isolated from different plants and dairy products from Qinghai-Tibet Plateau in China. The objective of this study was to perform genetic diversity analysis and explore the relationship between strains and isolate samples or separate regions. A total of 25 sequence types (STs) were identified with a diversity of up to 55.6%, which were grouped into one clonal complexes (CCs), 3 doublets and 17 singletons by eBURST. The results of minimum spanning tree and clustering analysis indicated these L. mesenteroides strains from the Qinghai-Tibet Plateau were relatively weakly related to the isolated region. However, there was a close relationship between the genotypes of L. mesenteroides strains and the type of the isolated sample, which was consistent with the results of API 50CH. The MLST scheme presented in this study provides a shareable and comparable sequence database and enhances our knowledge of the population diversity of L. mesenteroides strains which will be further used for the selection of industrial strains.