Background Adjuvant oral uracil-tegafur (UFT) has led to significantly longer postoperative survival among patients with non-small-cell lung cancer (NSCLC). Gemcitabine (GEM) monotherapy is also reportedly effective for NSCLC and has minor adverse events (AEs). This study compared the efficacy of GEM- versus UFT-based adjuvant regimens in patients with completely resected pathological stage (p-stage) IB–IIIA NSCLC. Patients and methods Patients with completely resected p-stage IB–IIIA NSCLC were randomly assigned to GEM or UFT. The primary endpoint was overall survival (OS); secondary endpoints were disease-free survival (DFS), and AEs. Results We assigned 305 patients to the GEM group and 303 to the UFT group. Baseline factors were balanced between the arms. Of the 608 patients, 293 (48.1%) had p-stage IB disease, 195 (32.0%) had p-stage II disease and 121 (19.9%) had p-stage IIIA disease. AEs were generally mild in both groups, and only one death occurred, in the GEM group. After a median follow-up of 6.8 years, the two groups did not significantly differ in survival: 5 year OS rates were GEM: 70.0%, UFT: 68.8% (hazard ratio 0.948; 95% confidence interval 0.73–1.23; P  = 0.69). Conclusion Although GEM-based adjuvant therapy for patients with completely resected stage IB–IIIA NSCLC was associated with acceptable toxicity, it did not provide longer OS than did UFT.