Depression predicts fall risk among older adults, and this relationship may be partially explained by depression-associated executive dysfunction, relevant to navigating demanding environments. This pilot study examined timed stepping accuracy under simple and complex dual-task conditions, using an instrumented walkway based on the Trail Making Test. Participants were balance-impaired older adults, either with (n = 8; major depressive disorder [MDD]) or without (n = 8; nondepressed [ND]) MDD. After accounting for comfortable gait speed and age, the MDD group was significantly slower than the ND group on the walkway with the highest cognitive demand and demonstrated greater dual-task cost, both of which were correlated with performance on traditional measures of executive functioning. No group differences were observed on the walkway with the least cognitive demand. Balance-impaired older adults with MDD demonstrate increased stepping accuracy time under cognitively demanding conditions, reflecting executive dysfunction and an additional contribution to increased fall risk.