This article considers how shifting programs of Aboriginal protection in nineteenth-century Australia responded to Indigenous mobility as a problem of colonial governance and how they contributed over time to creating an emergent discourse of the Aboriginal ‘‘vagrant.’’ When vagrancy laws were first introduced into Australia’s colonies, Aboriginal people were exempt from them as a group not yet subject to the ordinary regulatory codes of colonial society. Bringing them within the protective fold of colonial social order was one of the principal tasks of the office of ‘protection’ that was introduced into three Australian jurisdictions during the late 1830s. As the nineteenth century progressed and Aboriginal people became more susceptible to social order policing, a concept of Indigenous vagrancy hardened into place, and programs of protection became central to its management.