Walking is an everyday activity in our daily life. Because walking affects heart rate variability, in this research, for the first time, we analyzed the coupling among the alterations of the complexity of walking paths and heart rate. We benefited from the fractal theory and sample entropy to evaluate the influence of the complexity of paths on the complexity of heart rate variability (HRV) during walking. We calculated the fractal exponent and sample entropy of the R-R time series for nine participants who walked on four paths with various complexities. The findings showed a strong coupling among the alterations of fractal dimension (an indicator of complexity) of HRV and the walking paths. Besides, the result of the analysis of sample entropy also verified the obtained results from the fractal analysis. In further studies, we can analyze the coupling among the alterations of the complexities of other physiological signals and walking paths.