Background: The first-line combination of an epidermal growth factor receptor (EGFR) tyrosine kinase inhibitor (TKI) plus platinum-based doublet chemotherapy has yet to be sufficiently evaluated for patients with EGFR-mutant NSCLC. This randomized phase II trial was designed to identify an effective combined regimen of gefitinib (G) plus carboplatin/pemetrexed (CP) for subsequent use in phase III study. Methods: Chemotherapy-naïve patients with advanced non-squamous EGFR-mutated NSCLC were randomly assigned to receive either a concurrent regimen (C group) or a sequential and alternating regimen (S group). Patients in the C group received concurrent G (250 mg daily) and CP (AUC = 6 and 500 mg/m², day 1) of a 3-week cycle for 6 cycles, followed by concurrent G and P maintenance. Patients in the S group initially received G (days 1 to 28) and then CP (day 29 and 51); the cycle was repeated for 3 cycles, followed by alternating G and P maintenance. The primary endpoint was progression-free survival (PFS). Results: All 80 patients enrolled were eligible and evaluable for efficacy. Median PFS was 17.2 months in the C group and 15.1 months in the S group (p = 0.41). Although overall survival data are immature (with a median follow-up time of 24.6 months, 10 and 19 death events), median survival times were not reached in the C group, and were 30.0 months in the S group (p = 0.049). Response rates were similar in both groups (87.8% in the C group and 82.1% in the S group). The most common grade 3 or greater adverse events were neutropenia (48.8% and 46.2%), thrombocytopenia (41.5% and 28.2%), and anemia (34.1% and.12.8%). G-related skin rash or diarrhea was not severe, and interstitial lung disease was not frequent (two cases in each group; 5% of all patients). No treatment-related deaths occurred. Conclusions: To the best of our knowledge, this is the first randomized study to investigate the efficacy of a combination of EGFR-TKI and chemotherapy in the EGFR-mutated setting. Both regimens had promising efficacy with predictable toxicities, although concurrent regimens might provide better overall survival. Clinical trial information: UMIN000002789.