In the past fifteen years, increasing attention has been given to the role of Vocational Education and Training (VET) in attracting large numbers of international students and its contribution to the economic development of Australia. This trend has given rise to many challenges in vocational education, especially with regard to providing quality education that ensures international students stay in Australia is a satisfactory experience. Teaching and learning are continuously scrutinised, and teaching quality and student assessment are subject to regular audit (Takerei, 2010). VET teachers are key stakeholders in international education and share responsibility for ensuring international students gain quality learning experiences and positive outcomes; however, their experiences are generally not well understood. Therefore, this paper reports on a study which responded to this research gap and investigated particular challenges that VET teachers experience when teaching international students. The research participants were 15 teachers from several public and private VET institutions in Brisbane, Australia. The method involved responsive interviewing and inductive data analysis to identify and categorize teachers' challenges and dilemmas. After briefly outlining the background of the research approach, this paper presents findings about challenges that VET teachers' experienced while teaching international students. The aim of the paper is to explore VET teachers' perspectives in order to contribute essential understandings that contribute to a holistic approach to vocational education of international students. It reveals that the teachers experienced challenges of three main types: professional, personal and educational.