This study investigates the main effects of years of teaching experience and gender and their interaction effects on Iranian EFL teachers' sense of self-efficacy. To this end, the questionnaire of TEBS-Self (Teachers' Efficacy Beliefs System-Self) (Dellinger, Bobbett, Oliver, & Ellett, 2008) was used. It was distributed to 180 EFL teachers. 94 of them had taught for less than or equal to three years (G1), and 86 had taught for more than or equal to three and a half years (G2). Through regression analysis it was found that while experience and gender had no significant interaction effect on the participants' efficacy beliefs, G2 had significantly more positive efficacy perceptions than G1. Also, except for two components of TEBS-Self, the female teachers were found to have significantly higher self-efficacy than the male participants on the whole questionnaire and two components of it. Conclusions and suggestions for further research are also discussed.