Inclusion Criteria:

- Histologically or cytologically confirmed non-small cell lung cancer (NSCLC)

- Stage IIIB or IV disease

- Recurrent or progressive disease

- Measurable disease, defined as ≥ 1 unidimensionally measurable lesion ≥ 20 mm by
conventional techniques OR ≥ 10 mm by spiral CT scan

- Must have received prior treatment with platinum-based therapy and a taxane

- Asymptomatic brain metastasis allowed provided off steroids for > 2 weeks

- Zubrod performance status (PS) ≤ 2 OR Karnofsky PS 60-100%

- Life expectancy > 3 months

- Platelet count ≥ 100,000/mm³

- Bilirubin ≤ 2.0 mg/dL

- AST/ALT ≤ 2.5 times upper limit of normal

- Creatinine normal OR creatinine clearance ≥ 50 mL/min

- Not pregnant or nursing

- Negative pregnancy test

- Fertile patients must use effective contraception

- No neuropathy ≥ grade 2

- No uncontrolled illness including, but not limited to, any of the following:

- Ongoing or active infection

- Symptomatic congestive heart failure

- Unstable angina pectoris

- Cardiac arrhythmia

- Psychiatric illness or social situations that would preclude study compliance

- No other concurrent investigational agents

- At least 4 weeks since prior chemotherapy (6 weeks for nitrosoureas or mitomycin C)
and recovered

- At least 2 weeks since prior radiotherapy, including palliative radiotherapy, and
recovered

- No more than 2 prior chemotherapy regimens for NSCLC in the metastatic or adjuvant
setting

- No concurrent combination antiretroviral therapy for HIV-positive patients

Exclusion Criteria:

- Absolute neutrophil count ≥ 1,500/mm³

- No history of allergic reactions attributed to compounds of similar chemical or
biological composition to E7389