Many aspects of EFL teaching are negatively influenced by professional identity challenges which are not effectively responded to by EFL teachers. Considering this, few studies, however, have been conducted on EFL teachers’ professional identity challenges, and especially on their gender-specific challenges, and factors which can facilitate their professional identity construction. Therefore, this study, benefitting from a narrative inquiry method and using semi-structured interviews, aimed to examine the professional identity gender-specific challenges of six institute EFL teachers. The findings of this study showed that EFL male and female teachers were different in relation to the professional challenges they faced and a number of factors had caused this. Based on the overall findings, it is recommended that EFL teacher educators become aware of the challenges faced by teachers and factors which can affect their professional identity construction. Additionally, they need to help EFL teachers reduce the destructive effects of professional identity challenges by facing them and turning them into opportunities for learning.