We evaluated user perception of certain attention behaviours, eye head and body orientation in particular, of humanoid agents in a virtual environment for the purposes of interaction initiation. Users were shown a number of scenarios involving agents making gaze, gesture and locomotion behaviours and were asked to report their impressions of how attentive the agents were and their perceived likely-hood to engage in interaction. These evaluation studies are critical for furthering our understanding of the early phases of human-computer interaction where distance may be involved and there is uncertainty as to the intention of the other to interact. Amongst other results, we establish here that the human perception of interest, interaction seeking and openness from a humanoid agent is based, in part, on the time-varying behaviour of its eyes, head, body and locomotion directions. Application domains include social robotics and embodied conversational agents.