Given emerging evidence on their troubled transition to work, this study examines patterns, trends and changes in the labour market outcomes of international graduates remaining in Australia at 4 months following course completion between 1998 and 2015. Using the Australian Graduate Survey, this study shows that the share of international graduates who stayed on with the intention to work doubled during this period. The recent cohorts tended to come from non-English-speaking backgrounds, hold temporary visas and lack local work experience, all of which have been linked to disadvantageous labour market outcomes. This study further reveals a clear trend of rising economic inactivity, unemployment, part-time employment and qualification mismatch among international graduates over time, reflecting their vulnerability against a backdrop of socio-political and economic changes in the country. These findings indicate a need to review and strengthen existing policies and interventions to better help international graduates integrate into the labour market.