This phase I/II study was conducted to evaluate the safety and efficacy of tirapazamine in combination with cisplatin and vinorelbine for patients with advanced-stage IIIB/IV chemonaive non–small-cell lung cancer. Seventy patients with a Karnofsky performance status of ≥ 60% were included. In the phase I part of the study, 21 patients were treated on day 1 with tirapazamine (escalating doses of 260, 330, or 390 mg/m 2 ), cisplatin (75 or 100 mg/m 2 ), and vinorelbine (25 or 30 mg/m 2 ) for a maximum of 6 cycles every 4 weeks. Vinorelbine was repeated every week. In the phase II part of the study, 49 patients were treated on day 1 with tirapazamine 390 mg/m 2 , cisplatin 100 mg/m 2 , and vinorelbine 30 mg/m 2 . The maximum tolerated dose was not reached. Muscle cramps, vomiting, nausea, tinnitus, neutropenia, and diarrhea were the most frequently reported adverse events in the phase I part of the study. Most of these events were grade 1 or 2. In the phase II part of the study, response rate was 47%, and median survival was 50 weeks. The most frequently reported adverse event was neutropenia. Asthenia, fever, anemia, vomiting, weight decrease, nausea, and muscle cramps were also noted. For patients treated at the maximum dose, dose reductions occurred 14% of tirapazamine cycles and in 4% of cisplatin cycles. The median number of cycles was 3. This regimen has a manageable toxicity profile. Response rate and median survival suggest that this combination might be more active than the cisplatin/vinorelbine combination. This triplet is currently being evaluated in a phase III study.