In designing socially interactive robots we have focused on robot movement and its role in multi-modal human-robot communication. In this chapter we describe design and evaluation of robot body movements supporting communication, investigating the idea of using speed and orientation adjustments as design elements in human-robot interaction. The scenario studied includes a robotic shopping trolley that offers products via speech and GUI to the user while both are moving in a supermarket-like environment. Our results show that if the robot slows down while making such offers, users are more prone to react upon them and to take the product. However, even from our early pre-study with mock-up robots we observed that users tended not to mention the robot’s slow-down movements, even if these movements were shown several times to them during a video-based debriefing. This phenomenon, that users react implicitly on the robot’s movements without being consciously aware of them, was confirmed during an experimental study with a fully integrated robot prototype. We discuss our results by reflecting on human-robot interaction design methods, and we draw implications from the lessons learned in the study of the design of robot behaviours. In particular, we list a whole set of challenges for HRI when both the user and the robot are moving.