Visually guided animals depend heavily on the quality of visual signals in order to obtain functionally relevant information about their environment. To support visual information processing, nature has evolved a large variety of physiological adaptations and behavioral strategies such as compensatory head movements. During self-movement, head rotations compensate for changes in body attitude in order to stabilize gaze. However, how walking animals cope with uneven structured substrates, which may affect body and gaze orientation, is still unknown. We used stereo high-speed video to analyze compensatory head movements of blowflies walking freely on differently structured substrates. We found that even a pronounced asperity of the ground structure, with bumps of almost the size of the animal, was largely compensated by the walking apparatus of the blowfly, which leads to body roll and pitch movements only marginally larger than those on flat substrate. Pitch and roll fluctuations of the head were smaller compared with body fluctuations on all tested substrates, emphasizing the significance of gaze stabilization during walking on structured substrates. Furthermore, we found no impairment in head and body stabilization during walks in darkness, which indicates that the control system mediating compensatory head movements works well without any visual input. Interestingly, blowflies changed their walking style in the dark and seemed to use their forelegs as tactile probes.