The question of what makes a good teacher of English has aroused researchers' interest for many years, and the existing studies comparing NESTs (native English-speaking teachers) and NNESTs (non-native English-speaking teachers) have focused mostly on students' perceptions of these teachers. The current study aims to explore in the first phase if there is a meaningful difference between Turkish EFL learners' perceptions of NESTs and NNESTs on their first encounter with them. The second phase explores whether any changes have occurred in students' preconceptions regarding NESTs within the course of time. The participants are 120 Turkish monolinguals from a private university. Quantitative data was collected through questionnaires consisting of Likert-scale items in both phases. An interview session was added to the second phase to obtain more in-depth insights into students' perceptions. The findings showed that students had neutral perceptions of NESTs and NNESTs. However, in the second phase, the data analysed via qualitative content analysis demonstrated that students' perceptions were found to have positively changed for NESTs, particularly in terms of personality dimension. In both phases, students perceived NESTs in linguistic and professional dimensions, and NNESTs in pedagogical dimension rather positively.