Background: Accurate and timely molecular testing in patients with non-small cell lung cancer (NSCLC) is mandatory for targeted therapies and improved outcomes. Real-world obstacles, including geographic distance from specialized lung cancer services, along with comorbidities, may delay molecular diagnosis and subsequent treatment, therefore hampering survival. Methods: We conducted a retrospective, multi-departmental observational study of 927 patients with newly diagnosed NSCLC that were referred to a tertiary hospital in western Greece between January 2021 and December 2024. Patients were classified based on distance of residence (<30 km vs. ≥30 km). Clinical characteristics, time elapsed from pathological to final molecular diagnosis, and survival outcomes were analyzed and compared. Multivariable Cox regression was used to identify independent predictors of overall survival. Results: Patients residing ≥30 km away (61.2%) experienced delays in molecular testing (median 31 vs. 26 days, p = 0.002) and were less likely to undergo such testing (p = 0.012) compared to those residing 30 km also had a higher prevalence of COPD (42.5% vs. 31.2%, p = 0.002). Median survival from initial pathological diagnosis to death was significantly shorter in non-urban patients (129 vs. 215 days, p = 0.010). A molecular testing delay >35 days was independently associated with worse survival (HR = 0.684, 95% CI: 0.508–0.923, p = 0.013). No differences in TNM stage distribution were observed between geographical groups. Conclusions: Geographic disparities significantly impact access to advanced lung cancer services and molecular diagnostics and may provisionally affect prognosis in NSCLC. Improving testing pathways, incorporating reflex testing in pathological molecular analysis, and optimizing referral systems in rural areas may help to reduce inequalities and improve patient outcomes.