Purpose: To evaluate the efficacy and toxicity of bortezomib ± docetaxel as second-line therapy in patients with relapsed or refractory advanced non-small-cell lung cancer (NSCLC). Patients and Methods: Patients were randomly assigned to bortezomib 1.5 mg/m2 (arm A) or bortezomib 1.3 mg/m2 plus docetaxel 75 mg/m2 (arm B). A treatment cycle of 21 days comprised four bortezomib doses on days 1, 4, 8, and 11, plus, in arm B, docetaxel on day 1. Patients could receive unlimited cycles. The primary end point was response rate. Results: A total of 155 patients were treated, 75 in arm A and 80 in arm B. Baseline characteristics were comparable. Investigator-assessed response rates were 8% in arm A and 9% in arm B. Disease control rates were 29% in arm A and 54% in arm B. Median time to progression was 1.5 months in arm A and 4.0 months in arm B. One-year survival was 39% and 33%, and median survival was 7.4 and 7.8 months in arms A and B, respectively. Adverse effect profiles were as expected in both arms, with no significant additivity. The most common grade ≥ 3 adverse events were neutropenia, fatigue, and dyspnea (4% and 53%, 19% and 26%, and 17% and 14% of patients in arms A and B, respectively). Conclusion: Bortezomib has modest single-agent activity in patients with relapsed or refractory advanced NSCLC using this schedule, with minor enhancement in combination with docetaxel. Additional investigation of bortezomib in NSCLC is warranted in combination with other drugs known to be active, or using different schedules.