This paper proposes a new locomotion haptic interface, the Virtual Walking Machine (VWM) that can simulate human walking more naturally. The VWM allows walking in a virtual environment with uneven terrain, which can improve immersiveness significantly. The proposed system is composed mainly of: (i) a fifteen degree-of-freedom hybrid parallel mechanism that allows relative rotation between toe and heel, omni-directional rotation, and natural walking distance, (ii) Pulse Width Modulation (PWM) driven pneumatic actuators for vertical motion and servo-motors for planar motion, (iii) sensors that allow motion detection. Design requirements on natural walking are analyzed and used in conjunction with kinematic analyses to optimally design the proposed VWM.