The retention of international graduates has been deemed a viable approach to redressing skill shortages in many countries mainly owing to their local academic credentials. Notwithstanding, there is growing, albeit fragmented, evidence that international graduates who stayed on after course completion struggle to integrate into the host labour market. Building on this evidence, this study examines patterns, trends and changes in the labour market outcomes of international graduates who remained in Australia at four months after course completion between 1998 and 2015. Drawing on the Australian Graduate Survey, this study shows that the share of international graduates who stayed on with the intention to work more than doubled during this period. The more recent cohorts, however, tended to come from non-English-speaking backgrounds, stay on with temporary visas and lack local work experience, all of which have been linked to poorer outcomes in the Australian labour market. In fact, this study reveals a clear trend of increasing economic inactivity, unemployment, part-time employment and qualification mismatch amongst international graduates who remained in Australia over the years. The worsening labour market outcomes highlight the vulnerability of international graduates against a backdrop of socio-political and economic changes in Australia. These findings point to a need to review and strengthen existing policies and interventions to help international graduates integrate into the host labour market.