Service robots that mimic human social behavior can appear polite. We tested the social and behavioral efficacy and legibility of two kinesic courtesy cues on people's approval of a service robot. In a repeated-measures design, 29 volunteers were randomly assigned to two test situations: A participant and the robot simultaneously approached a bottleneck either next to each other or from opposite ends. Nested within these two situations were three courtesy cue conditions: The robot moved without any explicit courtesy cues, stopped, or moved aside and then stopped. We found statistically significant effects of the courtesy cues on people's self-reported appreciation and the legibility of the robot's motion. Behavioral observations indicated that the robot exhibiting two courtesy cues was less disruptive to the human's own actions and was thus more behaviorally effective. This research demonstrates that kinesic politeness cues can be used effectively in the motion design of service robots.