Purpose: A randomized three-arm phase II study was undertaken to evaluate the optimum administration schedule of pemetrexed and gemcitabine in chemotherapy-naïve patients with non-small-cell lung cancer. Patients and Methods: Patients were randomly assigned to three schedules of pemetrexed 500 mg/m2 plus gemcitabine 1,250 mg/m2, separated by a 90-minute interval, on a 21-day cycle as follows: schedule A, pemetrexed followed by gemcitabine on day 1 and gemcitabine on day 8; schedule B, gemcitabine followed by pemetrexed on day 1 and gemcitabine on day 8; and schedule C, gemcitabine on day 1 and pemetrexed followed by gemcitabine on day 8. Results: One hundred fifty-two eligible patients (schedule A, n = 59; schedule B, n = 31, and schedule C, n = 62) received a median of five (schedule A), two (schedule B), and four (schedule C) treatment cycles. Overall, 66% of patients experienced grade 3 or 4 neutropenia. Common grade 3 and 4 nonhematologic toxicities were dyspnea (11%), fatigue (16%), and transaminase elevation (9%). Schedule A seemed less toxic compared with schedule C (grade 3 or 4 events: 86% v 94%, respectively; P = .19; grade 4 events: 39% v 48%, respectively; P = .30). Schedule B was closed at interim analysis for inferior efficacy. Schedule A, with a confirmed response rate of 31% (95% CI, 20% to 45%), met the protocol-defined efficacy criteria, whereas schedule C, with a confirmed response rate of 16.1% (95% CI, 11% to 34%), did not. Median survival time and time to progression were 11.4 and 4.4 months, respectively, with no observable difference between the arms. Conclusion: Pemetrexed and gemcitabine administered as outlined for schedule A met the protocol-defined efficacy criteria, was less toxic compared with the other treatment schedules, and should be further evaluated.