Chinese Herb Medicine Formulas (CHMF) was reported to improve the quality of life (QoL) in advanced NSCLC patients. The present study was designed to investigate whether maintenance chemotherapy plus CHMF in patients would improve QoL and progression-free survival (PFS). Seventy-one patients were enrolled from 8 medical centers in China, and were randomly assigned to a maintenance chemotherapy plus CHMF group ( = 35) or a maintenance chemotherapy plus placebo group ( = 36). The outcome measures included PFS, Karnofsky performance status (KPS) scores, QoL (assessed with the lung cancer symptom scale (LCSS) questionnaire), and adverse events (AEs). Patients in the CHMF group showed significant improvements in median PFS (HR = 0.55, 95% CI 0.28-0.88, = 0.019), KPS scores ( = 0.047), fatigue (cycle [C] 3: = 0.03), interference with daily activities (C3: = 0.04) and dyspnea (C2: = 0.03) compared with patients in the placebo group. Compared with the placebo group, the incidence of AEs decreased in the CHMF group, including loss of appetite (C2: = 0.011, C4: = 0.004) and dry mouth (C4: = 0.011). The essential finding of our study is that maintenance chemotherapy combined with CHMF may prolong PFS, relieve symptoms, improve QoL and alleviate the side effects.