Responding to labour and skills shortages, Australia has developed a comprehensive immigration framework to attract and retain overseas graduates. While prior work has explored the post-graduation settlement patterns and work outcomes of overseas graduates, much less is known about the role of their country of origin on their labour market performances in the context of socio-economic and immigration policy changes. Drawing on the Australian Graduate Survey, this chapter explores the composition and labour market outcomes of overseas graduates who remained in Australia after graduation with a particular focus on the two largest source countries, China and India. Findings show that Chinese and Indian graduates are very highly educated, but they fare poorly in the labour market as compared with the locals, pointing to skill under-utilisation among overseas graduates. Nonetheless, their work and salary outcomes have improved over time, which may be attributed to the relaxation of post-graduation migration and employment pathways in Australia. While Chinese graduates struggle more in securing full-time employment, they are less susceptible to education-job mismatch relative to their Indian counterparts. The Chinese nationals may be working part-time for relevant work experience that may help to enhance their career prospects. These results are of importance to public policy in their capacity to highlight the issue of skill under-utilisation and the labour market integration patterns of overseas graduates as the socio-economic and immigration policy conditions shift over time.