The present study aimed at identifying a suitable multiscale entropy (MSE) algorithm for assessment of complexity in a stride-to-stride time interval time series. Five different algorithms were included (the original MSE, refine composite multiscale entropy (RCMSE), multiscale fuzzy entropy, generalized multiscale entropy and intrinsic mode entropy) and applied to twenty iterations of white noise, pink noise, or a sine wave with added white noise. Based on their ability to differentiate the level of complexity in the three different generated signal types, and their sensitivity and parameter consistency, MSE and RCMSE were deemed most appropriate. These two algorithms were applied to stride-to-stride time interval time series recorded from fourteen healthy subjects during one hour of overground and treadmill walking. In general, acceptable sensitivity and good parameter consistency were observed for both algorithms; however, they were not able to differentiate the complexity of the stride-to-stride time interval time series between the two walking conditions. Thus, the present study recommends the use of either MSE or RCMSE for quantification of complexity in stride-to-stride time interval time series.