Background: Survival benefit from chemotherapy in advanced hepatocellular carcinoma (HCC) was limited till now. New chemoregimens with cytotoxicity modulators were explored to improve efficacy. Chemotherapy modulated with valproic acid (VA) as a deacetylation inhibitor of histone and DNA damage response proteins, and hydralazine (HZ) as a DNA hypomethylating agent, hypothetically suppressing DNA repair, were used in phase II trial here for advanced HCC. Methods: Between July 2008 and March 2016, patients with chemo-naive advanced HCC, regardless of previous sorafenib treatment, not amenable to local therapy and with Child Pugh score ≤7, were treated with VA (200 mg thrice per day) and HZ (12.5 mg twice per day) in conjunction with gemcitabine and cisplatin (GCGG): gemcitabine (1000 mg/m2, D1; 800 mg/m2 D8, 15) and cisplatin (70 mg/m2, D1) every 28 days till disease progression and then with Dox-DTIC: doxorubicin (45 mg/m2) and dacarbazine (450 mg/m2) every 28 days. The primary endpoint was overall survival (OS); the secondary endpoints were safety, progression-free survival (PFS) and response rate (RR). Results: Thirty-seven patients with 16 sorafenib-experienced, underwent GCGG treatment, and 30 of them underwent the following Dox-DTIC treatment. The median OS was 14.6 months (95% confidence interval: 6.0–23.1). The median PFSs for patients treated with VA- and HZ-combined GCGG and Dox-DTIC were 3.7 and 4.2 months, respectively; the RRs were 10/37 (27.0%) and 7/30 (23.3%); and grade 3/4 neutropenia were 54% and 51%. However, there were no chemotherapy-related deaths. Conclusion: VA- and HZ-combined sequential chemotherapy was effective in advanced HCC with manageable toxicities.