How to effectively integrate culture into second language teaching has long been of concern in foreign language education. Despite advances in theory and practice for intercultural language teaching, there has been little research to investigate factors influencing teachers’ pedagogical beliefs and perceptions. This study addresses this gap by examining teachers’ perceptions of effective strategies that foster students’ intercultural competence in the teaching of Chinese as a foreign language and factors influencing their beliefs. Twenty-nine school and university teachers in Australia completed a survey and a focus group interview. Quantitative analyses revealed that teachers’ perceptions of the effectiveness of the strategies varied despite an overall positive attitude towards the teaching of culture. Their beliefs were significantly influenced by their years of teaching experience, educational setting, and native language, but not by gender, age group and educational backgrounds. Qualitative analyses attribute the inconsistency in teacher perceptions to teachers’ disparate conceptualisations of culture, teaching experiences, and educational contexts associated with different curricular and pedagogical requirements and learner characteristics. The findings reinforce the necessity for providing teachers with professional training, along with pedagogical guidance and resources in order to facilitate their intercultural language teaching practices.