Inclusion Criteria:

- Newly diagnosed, Stage IIIb or IV NSCLC, chemo or other systemic therapy naive

- One (1) unidimensionally measurable lesion

- ECOG Performance Status of 0 or 1, no peripheral neuropathy >Grade 1

- Patients with clinically stable brain metastases on a stable dose of (or no longer
requiring) dexamethasone at registration will be eligible. Patients who have received
cranial radiation for brain metastases must be at least 4 weeks from last radiation
treatment.

- Recovery in full from any previous surgical procedure

- No history of an acute cardiac or CNS event within 6 months of entry or current
clinical evidence of congestive heart failure or non-stable coronary artery disease

Exclusion Criteria:

- Hypersensitivity to any of the 4 study drugs

- Concurrent immunotherapy or participation in any investigational drug study within 4
weeks

- Serious uncontrolled intercurrent medical or psychiatric illness and organ allograft

- History of other malignancy within the last 5 years (except for squamous or basal
cell carcinoma of the skin, carcinoma in situ of the cervix, or superficial
transitional cell carcinoma of the bladder)

- Patient is a pregnant or lactating female