Background: Platinum-based chemotherapy with cetuximab is the standard of care for relapsed or metastatic squamous cell carcinoma of the head and neck (SCCHN). The aim of this trial was to investigate whether cetuximab and paclitaxel/carboplatin can achieve similar progression-free survival (PFS) with standard cetuximab and 5-FU/platinum-based chemotherapy. Standard chemotherapy treatment for SCCHN is related to severe toxicity and new, less toxic regimens are needed. Methods: In this multicentre, randomized, controlled, phase 2 trial, 85 patients with relapsed or metastatic SCCHN were randomized in a 1:1 ratio to cetuximab and 5-FU/cisplatin or carboplatin (arm A) vs. cetuximab and paclitaxel/carboplatin (arm B). Eligibility criteria included age ≥18 years, Eastern Cooperative Oncology Group (ECOG) performance status (PS) of 0–1, and adequate organ functions. The primary endpoint was to investigate whether PFS in arm B is significantly worse than PFS in arm A. Results: Median PFS in arm A was 4.37 months (95% CI: 2.9– 5.9 m) and 6.5 months (95% CI: 4.8–8.2 m) in arm B, (p = 0.064). Median overall survival (OS) was 8.4 months (95% CI: 5.3–11.5 m) in arm A and 10.2 months (95% CI: 5.4–15 m) in arm B, (HR = 0.71; 95% CI: 0.43–1.16). PFS HR for arm B was not significantly worse than arm A (HR = 0.65; 95% CI: 0.41–1.03). Adverse events ≥ grade 3 were more frequent in arm A than arm B (60% vs. 40%; p = 0.034). Conclusion: Cetuximab and paclitaxel/carboplatin was found to have similar efficacy and less toxicity compared to cetuximab and 5-FU/cisplatin or carboplatin. The experimental arm is easier to administer rendering it a favorable alternative to standard therapy.