Inclusion Criteria:

- Pathologically proven non-small cell lung cancer with evidence of distant
metastases/malignant pleural effusion

- Measurable disease on imaging studies in 2 dimensions

- No previous therapy with either paclitaxel or vinorelbine, or any chemotherapy for
the past five years

- Patients who have had a previous resection for their lung cancer and present with
recurrent disease will be eligible

- Patients with other prior malignancies will be included, provided they have been
disease-free for at least five years

- Patients with adequately treated basal cell or squamous cell carcinoma of the skin,
adequately treated carcinoma in-situ of the cervix and hormone sensitive prostate
cancer will be eligible

- Karnofsky score >= 70 (Eastern Cooperative Oncology Group [ECOG] 0-2)

- White blood cell (WBC) count >= 3,500/mm^3, OR

- Absolute neutrophil count (ANC) >= 1,500/ul

- Platelet count >= 100,000/mm^3

- Serum creatinine less than 1.5 times the upper limits of normal

- Serum aspartate aminotransferase (AST) and alanine aminotransferase (ALT) less than
1.5 times the upper limits of normal

- Serum alkaline phosphatase less than 2.5 times the upper limits of normal

- No active serious infections or other condition precluding chemotherapy

- Non-pregnant and non-nursing

- Men and women of reproductive potential may not participate unless they have agreed
to use an effective contraceptive method while on the study

- Able to give informed consent

- Able to return for treatment and follow-up as specified in the protocol

Exclusion Criteria:

- Known hypersensitivity to any component of vinorelbine or paclitaxel or other
required drugs in the study

- Any comorbidity or condition which, in the opinion of the investigator, may interfere
with the assessments and procedures of this protocol

- Inability to fulfill the requirements of the protocol