Background: It is still unknown if physiological complexity and autocorrelations (AC) of long-range stride interval (SI) time series are related to walking direction (WD) and application of galvanic vestibular stimulation (GVS). Methods and results: The SI fluctuations versus time for 34 healthy people walking 15 minutes on an instrumented treadmill is studied in four conditions: forward walking (FW) without GVS (FW_{S0}) and with GVS (FW_{S+}), and backward walking without GVS (BW_{S0}) and with GVS (BW_{S+}). The time series are then analysed from a spatio-temporal point of view and from a long-range AC point of view: particular attention is paid to the Hurst exponent (\alpha) and to the Minkowski fractal dimension, interpreted as indexes expressing predictability and complexity of the time series respectively. WD has a major impact on the results: walking backward increases spatio-temporal variablility and modifies long-range AC. GVS differently influences FW and BW: It increases the stride width in FW while increasing the mean SI duration in BW. The fractal dimension is always decreased when turning on GVS, but the long-range AC are unchanged. Conclusion: The control condition is typical of a chaotic system exhibiting long-range AC, and the trend of \alpha versus stride amplitude is compatible with a peculiar pendular model of walking. GVS reduced complexity or predictability, depending on WD. During FW walking, GVS reduced complexity, leading to fewer walking adaptability. During BW walking, GVS reduced predictability, leading to a more random walking. The present study thus opens a way to classify walking according to the complexity and predictability of SI time series. Our findings may finally have applications in the field of rehabilitation. They suggest that, in FW, GVS is a relevant tool to work on balance, while in BW, GVS may help to improve the regularity of steps.