We present a study whose goal is to investigate the role of immersive visual and auditory feedback to affect preferred walking pace and perceived ease and naturalness of walking actions. Additionally, we measured how the congruence between visual and auditory stimuli affects perceived ease of walking. The visual feedback was presented through a head mounted display and auditory feedback was delivered based on the detected footsteps of participants. Subjects were asked to walk in place on top of an aerobic stepper at the pace they preferred. Their tempo was detected while walking. After each trial the participants answered a series of questions. Results of the experiment show that different footstep sounds affect walking pace, visual feedback, however, did not influence the chosen walking pace. The questionnaire data indicate that perceived congruency between visuals and footstep sounds correlate with the rating of the ease of walking (the more congruent variables, the easier to walk for participants).