Introduction: We compared the stage at diagnosis for non-small cell lung cancer (NSCLC) patients in the military healthcare system (MHS) and the general public to assess differences between these two groups as well as to assess the trends in stage at diagnosis in the recent past. Method: This study was based on the non-identifiable data from the U.S. Department of Defense Automated Central Tumor Registry (ACTUR) and the Surveillance, Epidemiology, and End Results (SEER) program of the National Cancer Institute. Patients diagnosed with NSCLC between 1989 and 2012 were included. The distributions of tumor stage at diagnosis and trends in tumor stage were compared between the two populations. Results: The cohorts were predominately male in both ACTUR (65.3%) and SEER (55.1%) and white patients accounted for greater than 80% of patients in both ACTUR and SEER. Among 21,031 patients in ACTUR and 773,356 patients in SEER, stage IV lung cancers predominated (ACTUR 33.6%, SEER 40.5%) followed by stage III (ACTUR 26.1%, SEER 26.4%) and stage I (ACTUR 24.7%, SEER 20.6%). Notable differences between the two populations were the higher percentage of stage I and lower percentage of stage IV, along with a lower rate of unknown stage patients after 2004, in ACTUR than SEER. Between 1989 and 2012, the percentage of stage IV disease increased in ACTUR and SEER coincident with a decrease in unknown stage disease. Conclusions: The majority of NSCLC patients in the MHS and general population are diagnosed with stage IV NSCLC and the percentage is increasing. Compared to the general population, NSCLC patients in the MHS have a higher percentage of stage I, a lower percentage of stage IV, and of unknown stage cancer. Universal care along with more rigorous staging across the MHS may play a role in these findings.