Physical rotations and translations are the basic constituents of navigation behavior, yet there is mixed evidence about their relative importance for complex navigation in virtual reality (VR). In the present experiment, 24 participants wore head-mounted displays and performed navigational search tasks with rotations/translations controlled by physical motion or joystick. As expected, physical walking showed performance benefits over joystick navigation. Controlling translations via joystick and rotations via physical rotations led to better performance than joystick navigation, and yielded almost comparable performance to actual walking in terms of search efficiency and time. Walking resulted, however, in increased viewpoint changes and shorter navigation paths, suggesting a rotation/translation tradeoff and different navigation strategies. While previous studies have emphasized the importance of full physical motion via walking (Ruddle & Lessels, 2006, 2009), our data suggests that considerable navigation improvements can already be gained by allowing for full-body rotations, without the considerable cost, space, tracking, and safety requirements of free-space walking setups.