Purpose: The objective of this trial was to compare cisplatin-plus-vinorelbine regimen with cisplatin-plus-gemcitabine regimen in patients with stage IIIB-IV non-small cell lung cancer (NSCLC).Patients and Methods: Chemonaive patients with stage IIIB-IV NSCLC received either vinoelbine 30 mg/m2 (days 1 and 8) plus cisplatin 80 mg/m2 (day 1) every 21 days (VC arm) or gemcitabine 1250 mg/m2 (days 1 and 8) plus cisplatin 80 mg/m2 (day 1) every 21 days (GC arm).Results: One hundred thirty four patients (67 VC and 67 GC) were included to the study. Overall response rates for the VC arm (31.2%) were not significantly different from that of the GC arm (34.3%). There were no differences in overall survival and one-year survival rates. Median survival and one-year survival rates for the VC and GC groups were 10.6 and 11.5 months, 45% and 46.8%, respectively. Grade 3–4 thrombocytopenia was significantly higher on the GC arm (VC 1.4% v GC 8.9%, p 0.05), as was febrile neutropenia on the VC arm (VC 8.9% v GC 1.2%, p 0.05).Conclusion: VC and GC demonstrated similar efficacy but there were differences in toxicity profiles.