We prospectively analyzed p15 methylation patterns in 25 surgically resected tumors and 130 plasma, serum, and buffy coat samples from hepatocellular carcinoma (HCC) patients, controls with chronic hepatitis/cirrhosis, and healthy subjects. Using methylation-specific PCR, we demonstrated for the first time p15 promoter methylation in 64% of tumors and 25% (4 of 16) of patients' plasma and serum samples. Concurrent p15 and p16 methylation was shown in 48% of tumors, and p15/p16 methylation was detected in the plasma/serum of 92% (11 of 12) of patients. Of note, 75% of 12 patients with concurrent tumor methylation developed clinical metastasis/recurrence (P = 0.027). In buffy coat samples, p15 methylation was detected in all eight patients with tumor p15 methylation, suggesting the presence of circulating tumor cells. None of the control samples were methylation positive. Our data underscore the important role(s) of p15 and p16 methylation in hepatocarcinogenesis and tumor progression. Among 92% (23 of 25) of patients with tumor p15/p16 methylation, circulating tumor DNA and HCC cells were detected in the peripheral blood of 87% (20 of 23) of patients. The combination of these epigenetic markers may prove valuable for noninvasive HCC diagnosis and disease monitoring.