Australian state police have historically held wide-ranging powers which reflect their origins as all-encompassing administrators and agents of control over unruly colonial subjects. Contemporary police powers to stop and question individuals to establish whether they are lawfully present stem from at least 1958 when they were incorporated into section 188 of the Migration Act. There is no official monitoring of the use of stop and search powers in this or any other context, and the capacity for police to make on-the-spot checks has been enhanced by the establishment of the Immigration Status System which provides immediate feedback about immigration status, 24 hours a day. This paper will draw on statistical data, survey responses and interviews with senior New South Wales police to build up a picture of their immigration status checking practices, concentrating on opportunistic street encounters. The reported starting point - of directing attention to those who are perceived to be 'out of place' - embeds street-level border control into everyday practices of order maintenance policing. Questions of immigration status are found to be closely intertwined with determinations of identity, highlighting the importance in a globalising world of marking non-citizens as 'surveillable subjects', and raising deeper questions about entitlement and belonging.