The structure of the stride-to-stride time intervals during paced walking can be altered by the temporal pattern of the pacing cues, however, it is unknown if an altered probability distribution of these cues could also affect stride-to-stride time intervals. We investigated the effect of the temporal pattern and probability distribution of visual pacing cues on the temporal structure of the variability of the stride-to-stride time intervals during walking. Participants completed self-paced walking (SPW) and walking paced by visual cueing that had a temporal pattern of either pink noise presented with a normal distribution (PNND), shuffled pink noise presented with a normal distribution (SPNND), white noise presented with a normal distribution (WNND), and white noise presented with a uniform distribution (WNUD). The temporal structure of the stride-to-stride time intervals was quantified using the scaling exponent calculated from Detrended Fluctuation Analysis. The scaling exponent was higher during the SPW and PNND trials than during the SPNND, WNND and WNUD trials and it was lower during the WNUD trial compared to the SPNND trial. The results revealed that both the temporal pattern and the probability distribution of the visual pacing cues can affect the scaling exponent of the variability of the stride-to-stride time intervals. This information is fundamental in understanding how visual input is involved in the control of gait.