The post-translational modification of lysine acetylation is related to hepatocellular carcinoma (HCC), and understanding this relationship requires detailed knowledge about the acetylated proteome in HCC tissue and about differences in protein acetylation between cirrhosis and liver cancer. Here we characterized the acetylome in three paired sets of cirrhotic tissue and hepatitis B-related HCC tissue. Combining affinity-based enrichment of acetylated peptides with highly sensitive mass spectrometry, we identified 1493 acetylation sites in 777 proteins and quantified 1040 acetylation sites in 587 proteins. We discovered that the histone acetyltransferases p300 and CBP were hyperacetylated in HCC and cirrhosis but not in normal liver tissue. We also identified several proteins acetylated at more than 10 lysines in HCC and cirrhosis. In addition, our results revealed that HCC was associated with up-regulation of acetylation at 353 sites in 237 proteins and down-regulation of acetylation at 209 sites in 122 proteins. We validated our results using western blotting and immunohistochemistry. Validation with an independent set of clinical samples confirmed our initial screening result that acetylation of lysine 120 in histone H2B type 1-C/E/F/G/I and lysine 18 in histone H3.3 was significantly associated with survival of HCC patients. Acetylation of lysine 77 in histone H4 was associated with survival as well as recurrence. Our study provides numerous new leads to examine the role of acetylation in HCC and its potential as a prognostic marker as well as therapeutic target.