Immunotherapy in hepatocellular carcinoma based on one or a few tumor specific antigens have shown limited antitumor efficacy. As a major suppressive factor in tumor immune response, better understanding of the role of regulatory T cells (Tregs) in hepatocellular carcinoma might be important for design of future immunotherapy-based clinical protocols. Tregs from 49 HCC patients and 40 controls were identified by flow cytometric analysis for the phenotype. Functional studies were performed by analyzing their inhibition to immune responses. Finally investigating whether elimination of Tregs was capable of enhancing the immunostimulatory efficacy of NY-ESO-1b peptides. In HCC peripheral blood and tumor-infiltrating lymphocytes, we found increased numbers of Tregs, which expressed high levels of HLA-DR, GITR and CD103. The prevalence of Tregs increased with during progressive stages in HCC patients. Moreover, the elimination of Treg cells followed by stimulating with NY-ESO-1b peptide significantly improved the anti-tumor cytotoxic T lymphocytes responses in HCC patients compared with stimulating with NY-ESO-1b peptide alone. The immune response efficiency increased from 37.5 to 62.5%. In conclusion, the increase in frequency of Treg cells might play a role in suppression of the immune response against HCC and for the design of immunotherapy the incorporation of the Treg cell depletion strategy will achieve potent anti-tumor immunity with therapeutic impact.