This phase I/II trial is studying the side effects and best dose of azacitidine when given together with entinostat and to see how well they work in treating patients with recurrent advanced non-small cell lung cancer. Azacitidine and entinostat may stop the growth of tumor cells by blocking some of the enzymes needed for cell growth. Giving azacitidine together with entinostat may kill more tumor cells.

PRIMARY OBJECTIVES:

I. To assess safety, characterize toxicities, and determine the maximum tolerated dose of 5-AZA (azacitidine) with a fixed-dose of entinostat in patients with recurrent advanced non-small cell lung cancer (NSCLC). (Phase I) II. To determine the objective response rate of 5-AZA and entinostat in patients with recurrent NSCLC. (Phase II)

SECONDARY OBJECTIVES:

I. To determine the pharmacokinetic profile of 5-AZA and entinostat in patients with recurrent NSCLC.

II. To assess the pharmacodynamic effects of 5-AZA and entinostat on deoxyribonucleic acid (DNA) methylation, histone acetylation, and gene re-expression in patients with recurrent NSCLC through analysis of blood, sputum and tissue biopsies.

III. To explore the effect of 5-AZA and entinostat on progression-free and overall survival in patients with recurrent advanced non-small cell lung cancer.

IV. To explore the differing response rates and progression-free survivals of two schedules of 5-AZA and entinostat in patients with recurrent advanced non-small cell lung cancer.

OUTLINE: This is a multicenter, phase I, dose-escalation study of azacitidine followed by an open-label, phase II study.

Patients receive azacitidine subcutaneously (SC) on days 1-6 and 8-10 and entinostat orally (PO) on days 3 and 10. Treatment repeats every 28 days in the absence of disease progression or unacceptable toxicity.

After completion of study treatment, patients are followed up every 3 months.

Inclusion Criteria:

• Patients must have histologically or cytologically confirmed metastatic or unresectable NSCLC
• Patient must have failed at least one previous chemotherapy regimen
• 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 computed tomography (CT) scan
• Life expectancy of greater than 12 weeks
• Eastern Cooperative Oncology Group (ECOG) performance status (PS) =< 2 (Karnofsky >= 60%)
• Leukocytes >= 3,000/mcL
• Absolute neutrophil count >= 1,500/mcL
• Platelet count >= 100,000/mcL
• Total bilirubin within normal institutional limits
• Aspartate aminotransferase (AST) (serum glutamic oxaloacetic transaminase [SGOT] and alanine aminotransferase (ALT) (serum glutamic pyruvate transaminase [SGPT]) =< 2.5 x upper limit of normal
• Creatinine within normal institutional limits OR creatinine clearance >= 60 mL/min/1.73m^2 for patients with creatinine levels above institutional normal
• Women of child-bearing potential and men must agree to use adequate contraception (hormonal or barrier method of birth control; abstinence) prior to study entry and for the duration of study participation; should a woman become pregnant or suspect she is pregnant while participating in this study, she should inform her treating physician immediately
• Ability to understand and the willingness to sign a written informed consent document
• Patients who have a major objective response to treatment on this protocol, and who experience progression of disease at least 1 year after completion of protocol consent and therapy, may be re-treated at the previously effective dose and schedule

Exclusion Criteria:

• Patients who have had chemotherapy or radiotherapy within 4 weeks (6 weeks for nitrosoureas or mitomycin C) prior to entering the study or those who have not recovered from adverse events due to agents administered more than 4 weeks earlier
• Patients may not be receiving any other investigational agents
• Patients with uncontrolled brain metastases; patients with brain metastases must have stable neurologic status following local therapy (surgery or radiation) for at least 4 weeks, and must be without neurologic dysfunction that would confound the evaluation of neurologic and other adverse events
• Patients with liver metastases that replace greater than 30% of the liver parenchyma
• History of allergic reactions attributed to compounds of similar chemical or biologic composition to entinostat, 5-AZA, mannitol or other agents used in the study
• 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 on this protocol
• Human immunodeficiency virus (HIV)-positive patients on combination antiretroviral therapy are ineligible