Walking speed (WS) has emerged as a potential predictor of mortality in elderly cancer patients, yet data involving non-small-cell lung cancer (NSCLC) patients are scarce. Our prospective exploratory study sought to determine whether WS would predict early death or toxicity in patients with advanced NSCLC receiving first-line systemic intravenous treatment. Overall, 145 patients of ≥70 years were diagnosed with NSCLC over 19 months, 91 of whom displayed locally-advanced or metastatic cancer. As first-line treatment, 21 (23%) patients received best supportive care, 13 (14%) targeted therapy, and 57 (63%) chemotherapy or immunotherapy. Among the latter, 38 consented to participate in the study (median age: 75 years). Median cumulative illness rating scale for geriatrics (CIRS-G) was 10 (IQR: 8−12), and median WS 1.09 (IQR: 0.9−1.31) m/s. Older age (p = 0.03) and comorbidities (p = 0.02) were associated with Grade 3−4 treatment-related adverse events or death within 6 months of accrual. Overall survival was 14.3 (IQR: 6.1-NR) months for patients with WS < 1 m/s versus 17.3 (IQR: 9.2−26.5) for those with WS ≥ 1 m/s (p = 0.78). This exploratory study revealed WS to be numerically, yet not significantly, associated with early mortality in older metastatic NSCLC patients. Following these hypothesis-generating results, a larger prospective, multicenter study appears to be required to further investigate this outcome.