Background: Given the increase in incidence and mortality from cancer in recent years in Latin America and Peru, it is necessary to identify frailty older adults at higher risk of disability, hospitalizations and mortality. However, its measure is complex and requires time. For this reason, it has been proposed that frailty can be evaluated by a single measure, as gait speed. We aimed to evaluate the role of gait speed as a predictor of mortality in older men with cancer in Peru. Methods: A prospective cohort study was carried out that included military veterans (aged 60 years and older) with an oncological diagnosis evaluated at the Centro Médico Naval in Peru during the period 2013–2015. Slow gait speed was defined as <0.8 m/s. All-cause mortality was recorded during a 2-year follow-up. Sociodemographic characteristics, medical and personal history, and functional assessment measures were collected. We performed Cox regression analysis to calculate hazard ratios with their respective 95% confidence intervals. Results: 922 older men were analyzed from 2013 to 2015, 56.9% (n = 525) of whom were >70 years of age. 41.3% (n = 381) had slow gait speed with a mortality incidence of 22.9% (n = 211) at the end of follow-up. The most frequent types of cancer in the participants who died were of the lung and airways (26.1%), liver and bile ducts (23.2%), and lymphomas and leukemias (16.6%). In the adjusted Cox regression analysis, we found that slow gait speed was a risk factor for mortality in older men with cancer (adjusted hazard ratio = 1.55; 95% confidence interval: 1.21–2.23). Conclusions: Slow gait speed was associated with an increased risk of mortality in older men with cancer. Gait speed could represent a simple, useful, inexpensive, rapidly applicable marker of frailty for the identification of older men at higher risk of mortality. Gait speed could be useful in low- and middle-income countries, and in rural areas with limited access to health services.