Inclusion Criteria:

- Patients must have histologically confirmed non-small cell lung cancer

- No prior chemotherapy for advanced or metastatic disease

- ECOG performance status 0 or 1

- Patients must have measurable disease, defined as at least one lesion that can be
accurately measured in at least one dimension (longest diameter to be recorded) as >=
20 mm with conventional techniques or as >= 10 mm with spiral CT scan

- Life expectancy of greater than 12 weeks

- Leukocytes >= 3,000/mcL

- Absolute neutrophil count >= 1,500/mcL

- Platelets >= 100,000/mcL

- Total bilirubin within normal institutional limits

- AST(SGOT)/ALT(SGPT) =< 2.5 x institutional upper limit of normal

- Creatinine within normal institutional limits OR creatinine clearance >= 60
mL/min/1.73 m^2 for patients with creatinine levels above institutional normal

- Ability to understand and the willingness to sign a written informed consent document

Exclusion Criteria:

- Patients who have had chemotherapy or radiotherapy in a metastatic setting

- Patients may not be receiving any other investigational agents

- Patients with untreated brain metastases should be excluded from this clinical trial;
however, patients who have stable brain disease (should be off corticosteroids) at
least 3 weeks after completion of appropriate therapy are eligible

- Patients who have received any prior HDAC inhibitor (except valproic acid for seizure
control provided that the valproic acid has been stopped at least 30 days before
beginning therapy on this protocol) are excluded from this study

- Peripheral neuropathy of severity greater than grade 1

- Known history of allergic reactions to paclitaxel

- Prior therapy with paclitaxel

- Inability to take oral medications on a continuous basis; patients unable to swallow
the vorinostat capsules whole are ineligible (the capsules cannot be crushed or
broken)

- Uncontrolled intercurrent illness including, but not limited to, ongoing or active
infection, symptomatic congestive heart failure, unstable angina pectoris, cardiac
arrhythmia, or psychiatric illness/social situations that would limit compliance with
study requirements

- Pregnant women are excluded from this study; breastfeeding should be discontinued if
the mother is treated with vorinostat; women of childbearing potential must use an
appropriate double barrier method of birth control (such as female use of a
diaphragm, intrauterine device [IUD], sponge and spermicide, in addition to the male
use of a condom) or a prescribed birth control implant or practice abstinence; both
double barrier contraception and implants must be used for at least one week prior to
the start of the research study and continue for at least two weeks following the
last study visit; please note that birth control pills should not be used while on
this study as they may have a negative interaction with the experimental drug in this
study

- HIV-positive patients receiving combination antiretroviral therapy are ineligible