Objectives: This pilot study assessed whether frontal lobe transcranial direct current stimulation (tDCS) combined with complex walking rehabilitation is feasible, safe, and shows preliminary efficacy for improving walking and executive function. Materials and Methods: Participants were randomized to one of the following 18-session interventions: active tDCS and rehabilitation with complex walking tasks (Active/Complex); sham tDCS and rehabilitation with complex walking tasks (Sham/Complex); or sham tDCS and rehabilitation with typical walking (Sham/Typical). Active tDCS was delivered over F3 (cathode) and F4 (anode) scalp locations for 20 min at 2 mA intensity. Outcome measures included tests of walking function, executive function, and prefrontal activity measured by functional near infrared spectroscopy. Results: Ninety percent of participants completed the intervention protocol successfully. tDCS side effects of tingling or burning sensations were low (average rating less than two out of 10). All groups demonstrated gains in walking performance based on within-group effect sizes (d ≥ 0.50) for one or more assessments. The Sham/Typical group showed the greatest gains for walking based on between-group effect sizes. For executive function, the Active/Complex group showed the greatest gains based on moderate to large between-group effect sizes (d = 0.52–1.11). Functional near-infrared spectroscopy (fNIRS) findings suggest improved prefrontal cortical activity during walking. Conclusions: Eighteen sessions of walking rehabilitation combined with tDCS is a feasible and safe intervention for older adults. Preliminary effects size data indicate a potential improvement in executive function by adding frontal tDCS to walking rehabilitation. This study justifies future larger clinical trials to better understand the benefits of combining tDCS with walking rehabilitation.