Researchers, game designers, and consumers place great hopes into the potential benefits of virtual reality (VR) technology on the user experience in digital games. Indeed, initial empirical research has shown that VR technology can improve the gaming experience in a number of ways compared to traditional desktop gaming, for instance by amplifying immersion and flow. However, on the downside, a mismatch between physical locomotion and the movements of the avatar in the virtual world can also lead to unpleasant feelings when using VR technology—often referred to as cybersickness. One solution to this problem may be the implementation of novel passive repositioning systems (also called omnidirectional treadmills) that are designed to allow a continuous, more natural form of locomotion in VR. In the current study, we investigate how VR technology and the use of an omnidirectional treadmill influence the gaming experience. Traditional desktop gaming, VR gaming, and omnidirectional treadmill gaming are compared in a one-factorial experimental design (N = 203). As expected, we found that VR gaming on the one hand leads to higher levels of flow, presence, and enjoyment, but at the same time also is accompanied by higher levels of cybersickness than traditional desktop gaming. The use of the omnidirectional treadmill did not significantly improve the gaming experience and also did not reduce cybersickness. However, this more physically demanding form of locomotion may make omnidirectional treadmills interesting for exergame designers.