Coordination between visual and motor processes is critical for the selection of stable footholds when walking in uneven terrains. While recent work (Matthis et al. in Curr Biol 8(28):1224-1233, 2018) demonstrates a tight link between gaze (visual) and gait (motor), it remains unclear which aspects of visual information play a role in this visuomotor control loop, and how the loss of this information affects that relationship. Here we examine the role of binocular information in the visuomotor control of walking over complex terrain. We recorded eye and body movements while normally-sighted participants walked over terrains of varying difficulty, with intact vision or with vision in one eye blurred to disrupt binocular vision. Gaze strategy was highly sensitive to the complexity of the terrain, with more fixations dedicated to foothold selection as the terrain became more difficult. The primary effect of increased sensory uncertainty due to disrupted binocular vision was a small bias in gaze towards closer footholds, indicating greater pressure on the visuomotor control process. Participants with binocular vision losses due to developmental disorders (i.e., amblyopia, strabismus), who have had the opportunity to develop alternative strategies, also biased their gaze towards closer footholds. Across all participants, we observed a relationship between an individual's typical level of binocular visual function and the degree to which gaze is shifted toward the body. Thus the gaze-gait relationship is sensitive to the level of sensory uncertainty, and deficits in binocular visual function (whether transient or long-standing) have systematic effects on gaze strategy in complex terrains. We conclude that binocular vision provides useful information for locating footholds during locomotion. Furthermore, we have demonstrated that combined eye/body tracking in natural environments can be used to provide a more detailed understanding of the impact of a type of vision loss on the visuomotor control process of walking, a vital everyday task.