The records of colonial Australia, where unfree work and outputs were systematically recorded across many years, constitute an astonishingly vast and rich labour history archive, much of it recorded in tabular form and thus immediately suited to transcription and digital analysis. In this article, we depart from conventional tabular data constructs and employ graph database technology, enabling us to investigate the structured and unstructured contents of our records. Employing this technology, we investigate a cohort of around 2,000 male convicts in the early colony of New South Wales, tracking their working lives through their arrival, servitude and emancipation. We trace their changing occupations and where they lived and worked after they gained freedom to choose their own employment. As a result, we discover that the occupations of convicts during the period 1822-28 were highly dynamic, with the data also suggesting social connections between convicts played a diminished role in free worker migrations and employment. Through this demonstration of a new technology and method, we open the door to more nuanced ways of locating workers and labour in the archives.