Inclusion:

1. Ability to understand and the willingness to sign a written informed consent. A signed informed consent must be obtained prior to any study specific procedures.
2. Patients must have Stage IIIB (with malignant pleural effusions) or Stage IV histological or cytological confirmation of non-small cell carcinoma (excluding squamous).
3. Age >/= 18 years old
4. Patients must have at least 1 measurable lesion. Lesions must be evaluated by computed tomography (CT) scan or magnetic resonance imagining (MRI)
5. ECOG Performance Status of 0 - 1
6. Controlled blood pressure (defined as systolic BP </= 150mmHg and diastolic </= 90 mmHg)
7. Adequate bone marrow, liver and renal function as assessed by the following laboratory requirements to be conducted within 7 days prior to start of first dose: Hemoglobin >/= 9.0 g/dL; White blood cell (WBC) count >/= 2,500/mm3, Absolute neutrophil count (ANC) >/= 1,500/mm3, Platelet count >/= 100,000/mm3, Total bilirubin </= 1.5 times the upper limit of normal (ULN), ALT and AST </= 2.5 x ULN (</=5 x ULN for patients with liver involvement), INR </= 1.5 and aPTT within normal limits.
8. Inclusion Criteria #7: Serum creatinine </= ULN or creatinine clearance (CrCl) >/= 45 mL/min (CrCl = Wt (kg) x (140 - age)/72 x Cr level, female x 0.85) for patients with creatinine levels above institutional normal. Urinalysis (UA) must show less than 1+ protein urine, or the patient will require a repeat UA. If repeat UA shows 1+ protein or more, a 24 hour collection will be required and must show total protein </= 1000 mg/24 hour to be eligible
9. Women of childbearing potential must have a negative serum pregnancy test performed within 7 days prior to start of treatment.
10. Women of childbearing potential and men must agree to use adequate contraception prior to study entry and for the duration of study participation, including the 30 day period after last study drug dosing. The investigator should advise the patient what is considered adequate contraception.

Exclusion:

1. Patients with squamous histology.
2. Cardiac disease: Congestive heart failure (CHF) > Class II NYHA; active coronary artery disease (myocardial infarction) [MI] more than 6 months prior to study entry is allowed); or serious cardiac ventricular arrhythmias requiring anti-arrhythmic therapy (beta-blockers or digoxin are permitted)
3. Uncontrolled hypertension defined as systolic blood pressure > 150 mmHg or diastolic pressure > 90 mmHg despite optimal medical management
4. Human Immunodeficiency Virus (HIV) infection or chronic hepatitis B or C
5. Active clinically serious infections (> Grade 2 NCI-CTC Version 3.0)
6. History of brain metastases. Patients with history of brain metastases are eligible as long as the metastasis has been treated with either stereotactic whole brain radiation or neurosurgery, patient does not require ongoing treatment with dexamethasone and patient's radiographic imaging is stable >/= 4 weeks from start of treatment. Time from brain metastasis treatment to first study treatment must meet the following criteria: Stereotactic whole brain radiation >/= 4 weeks from first study treatment, Neurosurgery >/= 24 weeks from first study treatment, continued in exclusion # 7
7. Continued from exclusion criterion # 6: Brain biopsy >/= 12 weeks from first study treatment.
8. Uncontrolled seizure disorder. Use of cytochrome P450 enzyme-inducing antiepileptic drugs (phenytoin, carbamazepine or phenobarbital) is not allowed
9. Thrombotic or embolic events such as cerebrovascular accident, transient ischemic attacks, deep vein thrombosis or pulmonary embolism
10. Organ allograft
11. Evidence or history of bleeding diathesis or coagulopathy
12. History of/or current evidence of hemoptysis (bright red blood of 1/2 teaspoon or more)
13. Peripheral neuropathy >/= Grade 2
14. Anticancer chemotherapy or immunotherapy: Anticancer therapy is defined as any agent or combination of agents with clinically proven anticancer activity administered by any route with the purpose of affecting the cancer, either directly or indirectly, including palliative and therapeutic endpoints (except patients who have received adjuvant chemotherapy > 52 weeks from Cycle 1 Day 1)
15. Radiotherapy to the target lesions within 3 weeks of start of first dose. Toxicities from radiotherapy must have resolved prior to start of first dose.
16. No major surgery, open biopsy or significant traumatic injury within 4 weeks of start of first dose
17. Serious, non-healing wound, ulcer, or bone fracture
18. Granulocyte growth factors (G-CSF), within 3 weeks of study entry.
19. Patients taking chronic erythropoietin are permitted provided no dose adjustment is made within 2 months prior to start of first dose
20. Pregnant or breast feeding patients
21. Substance abuse, medical, psychological or social conditions that may interfere with the patient's participation in the study or evaluation of the study results
22. Known or suspected allergy to any recombinant human antibodies, or compounds of similar chemical or biologic composition to sorafenib or any of the drugs in this study
23. Any condition that is unstable or could jeopardize the safety or compliance of the patient in the study
24. Previous or concurrent cancer that is distinct in primary site or histology from the cancer being evaluated in the study EXCEPT cervical cancer in situ, treated basal cell carcinoma, superficial bladder tumors (Ta, Tis, and T1) or any cancer curatively treated > 3 years prior to study entry
25. Any condition that impairs the patient's ability to swallow pills as a whole
26. Any malabsorption conditions
27. Therapeutic anticoagulation with warfarin, heparins, or heparinoids
28. Patients takin phenytoin, carbamazepine, and Phenobarbital
29. Patients taking rifampin, St. John's Wort