This paper explains a control and navigation algorithm of a 6-DOF gait rehabilitation robot, which can allow a patient to navigate in virtual reality (VR) by upper and lower limbs interactions. In gait rehabilitation robots, one of the important concerns is not only to follow the robot motions passively, but also to allow the patient to walk by his/her intention. Thus, this robot allows automatic walking velocity update by estimating interaction torques between the human and the upper limb device, and synchronizing the upper limb device to the lower limb device. In addition, the upper limb device acts as a user-friendly input device for navigating in virtual reality. By pushing the switches located at the right and left handles of the upper limb device, a patient is able to do turning motions during navigation in virtual reality. Through experimental results of a healthy subject, we showed that rehabilitation training can be more effectively combined to virtual environments with upper and lower limb connections. The suggested navigation scheme for gait rehabilitation robot will allow various and effective rehabilitation training modes.