The spatial behavior of robots working alongside humans critically influences the experience of comfort and personal space of users. The spatial behavior of service robots is especially important, as they move in close proximity to their users. To identify acceptable spatial behavior of Follow Me robots, we conducted an experimental study with 24 participants. In a within-subject design, human-robot distance was varied within the personal space (0.5 and 1.0 m) and social space (1.5 and 2.0 m). In all conditions, the robot carried a personal item of the participants. After each condition, the subjective experience of users in their interaction with the robot was assessed on the dimensions of trust, likeability, human likeness, comfort, expectation conformity, safety, and unobtrusiveness. The results show that the subjective experience of participants during the interaction with the Follow Me robot was generally more positive in the social distance conditions (1.5 and 2.0 m) than in the personal distance conditions (0.5 and 1 m). Interestingly, the following behavior was not perceived as comparable to humanhuman following behavior in the 0.5 and 2.0 m conditions, which were rated as either closer than human following or further away. This result, in combination with the more positive user experience in the social space conditions, illustrates that an exact transfer of interaction conventions from human-human interaction to human-robot interaction may not be feasible. And while users generally rate the interaction with Follow Me robots as positive, the following-distance of robots will need to be considered to optimize robot-behavior for user acceptance.