This study explored graduate pre-service teachers' language learning strategies and language self-efficacy and the relationship between these two constructs. Seventy-four graduate English-as-a-second-language (ESL) pre-service teachers (13 males, 61 females) from a teachers' college in Kuching, Sarawak, Malaysia, participated in this study. These pre-service teachers were in a one-year Diploma in Education course to prepare them to teach English in school. Six categories of language learning strategies were identified from their responses to seven hypothetical learning contexts. Pearson correlation coefficients show that there was a significant positive relationship between language learning strategies and language self-efficacy. Interview findings were in agreement with the above findings. High self-efficacy pre-service teachers reported more frequent use of more number of language learning strategies than did low self-efficacy pre-service teachers. Implications and suggestions for further research are put forward. (Contains 2 tables.)