The purpose of this study was to determine the maximum tolerated dose, toxicity profile and anti-tumor activity of paclitaxel in combination with gemcitabine when administered to patients with unresectable locally recurrent or metastatic squamous cell carcinoma of the head and the neck (SCCHN). Twenty-seven patients were treated in a phase I-II study with gemcitabine at a dose of 800 mg/m on days 1 and 8, escalating to a dose of 1,000 mg/m, plus escalating doses of paclitaxel (100, 135 and 175 mg/m) on day 2. Treatment consisted of 6 cycles repeated every 3 weeks. The main toxicity was myelosuppression. Other toxicities were mild and manageable. Due to grade 4 neutropenia at higher doses the recommended dose level of the gemcitabine/paclitaxel combination was 1,000/135 mg/m. Four patients achieved a partial response and no patient had a complete remission, giving an overall response rate of 14.8%. The median time of survival was 24 weeks. We conclude that the combination of paclitaxel and gemcitabine is tolerated, but shows insufficient clinical activity in patients with recurrent and/or metastatic SCCHN to warrant further testing.