Background: Non-small cell lung cancer (NSCLC) accounts for the majority of lung cancer diagnoses. Previous literature has evaluated associations between physical factors and outcomes in NSCLC. Throughout these studies, important physical factors that affect overall survival (OS) in NSCLC patients are body mass index (BMI) and serum albumin (SA) levels. In terms of BMI, previous research has come across the “obesity paradox.” That is, presenting an obese BMI serves as a protective role in patient survival. Hypoalbuminemia, defined as SA levels < 3.5 g/dL, has been shown to have a significantly adverse effect on both early and late stage patients’ outcomes. Our study aims to analyze the role of BMI and SA in patients with advanced-stage NSCLC. Methods: This retrospective study includes 112 patients with stage III and stage IV NSCLC identified between January 1st, 2014 through December 31st, 2018. Categorical and continuous analyses (Pearson’s chi-square and Kruskal-Wallis test) were performed to analyze the associations between median OS, BMI, and SA. BMI subgroups are classified according to the Center for Disease Control guidelines. BMI and SA are calculated at time of diagnosis. OS is defined as the date of diagnosis until the date of death. Other notable confounders investigated include treatment modality, histology, and comorbidities. Results: Of the 112 patients, 57% of patients identified as male. The study population mean age was 73 years. The majority (88%) of patients identified as white. The median BMI was 26.1, with 26% of patients presenting as obese. The median SA level of the population was 3.8 g/dL, with 34% of patients presenting as hypoalbuminemic. Study population median OS was 0.734 years. Median OS for the obese BMI subgroup was 1.42 years, compared to 0.70, 0.71, and 0.42 years for overweight, normal, and underweight BMI, respectively. Kruskal-Wallis analyses confirm that patient BMI plays a significant difference in terms of OS, with a significant subgroup difference between patients with obese and underweight BMIs (p = 0.05). Regarding SA, both chi-square and Kruskal-Wallis tests confirm that at the time of diagnosis, patients with normal SA have a longer median OS compared to their hypoalbuminemic counterparts (median OS 1.29 years vs 0.32 years, respectively; OR = 6.72, 95% CI [2.48, 18.22], p < 0.001). Conclusions: Our study reveals that an obese BMI plays a significant protective role regarding OS when evaluating prognostic outcomes between obese and underweight patients. Further, as SA levels are a known biomarker for nutritional status, our study highlights the importance of nutritional and educational optimization among healthcare professionals and patients alike prior to the diagnosis of malignancy. Future large prospective cohort studies are needed to analyze the efficacy of nutritional optimization, and further justify the “obesity paradox” and its underlying framework.