Functional defects in natural killer (NK) cells have been proposed to be responsible for the failure of anti-tumor immune responses. Whether and how NK cells are impaired in hepatocellular carcinoma (HCC) patients remain unknown. In this study, we found that HCC patients displayed a dramatic reduction in peripheral CD56(dim)CD16(pos) NK subsets compared with healthy subjects. A significant reduction of CD56(dim)CD16(pos) NK subsets was also found in tumor regions compared with non-tumor regions in the livers of these HCC patients. Both these peripheral and tumor-infiltrating NK cells exhibited poorer capacity to produce IFN-gamma and kill K562 targets, which was further found to be associated with increased CD4(+)CD25(+) T regulatory cells as we previously-described in HCC patients. Addition of Tregs from HCC patients efficiently inhibited the anti-tumor ability of autologous NK cells in vitro. These findings are helpful for understanding the mechanism of NK cell-mediated anti-tumor immune responses in HCC patients.