In immersive Virtual Reality (VR), computationally-mediated worlds allow participants to immersively experience virtual environments, to alter physics in a way that it is not possible in the real world, and to move their body and control their virtual movements in innovative and novel ways. Being able to fly is an experience that humans have long dreamed of achieving. In this paper, we introduce a VR game where participants can use their body gestures as a Natural User Interface (NUI) to control flying movements via a Microsoft Kinect. Furthermore, we conducted a mixed-methods study to explore the ways in which people want to control their flying movements in VR through physical gestures, and we evaluated the ease of use of the flying movement controls. The results revealed that when people map their physical gestures to flying movements in VR, certain gestures are easier to control and interact with.