The purpose of this study was to screen desirable yeast strains for alcoholic fermentation of tomato paste without sugar addition. The moisture, crude protein, crude fat, ash, and soluble nitrogen contents of the tomato paste (25 °Brix) were found to be 67.33%, 1.90%, 0.03%, 0.02%, and 30.72%, respectively. Free sugars found in the paste were fructose and glucose. Most abundant free amino acids of the paste were glutamic, aspartic, and γ-aminobutyric acids. Total seven yeast strains (Saccharomyces cerevisiae KDH (TWA), S. cerevisiae Lalvin ICVD-47 (TWB), S. cerevisiae Lalvin RC-212 (TWC), S. cerevisiae Lalvin K1-V1116 (TWD), S. bayanus Lalvin EC-1118 (TWE), S. cerevisiae Enoferm (TWF), and S. cerevisiae DJ97(KCTC8842P) (TWG)) were tasted for alcohol fermentation of the tomato paste. The highest alcohol content (8.2%) and the lowest residual sugar content (13.25 °Brix) were observed in the tomato paste fermented using the S. cerevisiae Lalvin ICVD-47 strain (TWB) after 3 day and 4 day of fermentation, respectively. Sugar and reducing sugar contents, and pH of the tomato paste were not remarkably affected by the difference in yeast strains used, showing 13.25~13.45 °Brix, 28.37~28.48 mg/mL, and 4.43~4.54, respectively, after 4 day of fermentation. Color and total acid content were significantly affected by the types of yeast strains and fermentation time, but the numerical changes were negligible. These results indicate that TWB would be the suitable strain for alcoholic fermentatiom of tomato paste based on its highest alcohol production and the lowest residual sugar content produced during fermentation.