International graduates have been shown to struggle in their transition to the host labour market after course completion. In Australia, international graduates typically fare worse than domestic graduates in the labour market, with new evidence pointing to a deterioration in their relative labour market position over the years. The contributing factors for the deterioration, however, remain unclear. In this article, we analysed unique large-scale survey data from the Australian Graduate Survey to identify the factors underlying the deteriorating labour market outcomes of international graduates from 2000. Our findings indicate that the deteriorating labour market outcomes of international graduates can be largely linked to the declining share of these graduates who are a citizen or permanent resident of Australia. The rising percentage of international graduates who are non-native English-speakers also played a role, albeit a modest one. These findings call attention to the persistent labour market disadvantage of international graduates and highlight the inadequacies of existing policies aimed at temporary retention and stronger English language skills in promoting labour market integration.