Background: Complex walking conditions (e.g. dual tasking) have been associated with increased prefrontal (PFC) activity. However, most paradigms include a predictable environment, specifically, a predictable walking terrain. In the present study we investigate PFC activity under an unusual walking condition where each foot placement was on unexpected terrain, thus causing a mismatch between visuospatial perception and lower-extremity proprioception. Research objective: To assess whether PFC activity increases under unstable unpredictable conditions compared to unstable but predictable conditions. Methods: This was a prospective study involving twenty healthy adults. Participants walked in two conditions: unstable but predictable, and unstable and unpredictable. To assess walking stability, both stride-time (ST) and stride-time variability (CV) were measured. To assess PFC activity, two wireless near-infrared spectroscopy devices were used. The group hemodynamic response (GHR) was calculated for each condition. For statistical analysis, a linear-mixed-effects model was used. Results: Walking with unpredictable perturbations did not change the ST (t = 0.51, p = 0.61) but significantly increased the parameter CV (t = 11.74, p < 0.001). The GHR of both conditions indicated brief per-initiation PFC activity that was similar across conditions. However, when GHRs were calculated relative to normal walking (i.e., the participants' own shoes), continuous activity was evident. Compared to the predictable condition, the unpredictable condition significantly increased this activity during steady-state walking (t = 2.13, p = 0.033). Significance: Observations from the present study suggest that at least two neural components are present in the measured signal—a brief one, occurring per-initiation, and a continuous one, sensitive to the predictability of the terrain. The second component was accompanied by a decrease in walking stability. These results may contribute to our understanding of the control mechanism underlying gait and future planning of rehabilitation protocols.