Due to advances in technology, the world around us contains an increasing number of robots, virtual agents, and other intelligent systems. These systems all have a certain degree of autonomy. For the people who interact with an intelligent system it is important to obtain a good understanding of its degree of autonomy: what tasks can the system perform autonomously and to what extent? In this paper we therefore present a study on how a system’s characteristics affect people’s perception of its autonomy. This was investigated by asking fire-fighters to rate the autonomy of a number of search and rescue robots in different shapes and situations. In this paper, we identify the following seven aspects of perceived autonomy: time interval of interaction, obedience, informativeness, task complexity, task implication, physical appearance, and physical distance to human operator. The study showed that increased disobedience, task complexity and physical distance of a robot can increase perceived autonomy.