Background The aim of our study was to determine the maximum tolerated dose of paclitaxel combined with a fixed dose of gemcitabine and vinorelbine in the treatment of non-small-cell lung cancer (NSCLC) and to evaluate in a phase II trial the efficacy of this combination. Patients and methods Sixty-two patients with stage IIIB/IV NSCLC were treated with paclitaxel in escalating doses from 40–80 mg/m2 combined with gemcitabine and vinorelbine at fixed doses of 1000 mg/m2 and 25 mg/m2, respectively. All drugs were given intravenously on day 1 and 8 every3 weeks. Results In a phase I trial, carried out on 21 patients, grade 4 neutropenia, as dose-limiting toxicity, occurred at the dosage level of paclitaxel 80 mg/m2. In a phase II trial, with paclitaxel administered at70 mg/m2, 27 out of 41 (66%) assessable patients responded (10% complete responses and 56% partial responses). Objective response was observed in 13 of 16 patients (81%) with stage IIIB diseaseand in 14 of 25 (56%) with stage IV disease. The median time to treatment failure was 26 weeks (range 3–72 weeks; 32 weeks and 20 weeks for stages IIIB and IV, respectively) and median survival62 weeks (range 4–176 weeks; 72 weeks and 56 weeks for stages IIIB and IV, respectively). One-year survival was 64% for all patients (72% for patients with stage IIIB and 52% for those with stage IV). Grade 3 and 4 neutropenia were observed in 11 (27%) and seven (17%) cases, respectively; grade 3 thrombocytopenia was observed in three patients (7%) and grade 3 anemia in four patients (10%). The most relevant non-hematological toxicity was grade 2/3 asthenia, which was observed in 12 patients (29%). Alopecia was almost universal, whereas nausea and vomiting were absent. Conclusions The combination of paclitaxel, gemcitabine and vinorelbine is effective and tolerable in the treatment of NSCLC. The high activity and low toxicity of this regimen warrant randomized studies with platinum-containing combinations.