Variability appears to be a worthwhile strand for research in SLA arising out of the realistic, communicative approach to language learning. In accounting for variability, different frameworks have been proposed, each focusing on certain aspects of the learners. Gender is an instance of the variables that is “always present but not always apparent” (Sunderland, 2000, p. 203). In addressing the gap in literature on the relationship between gender, task and variable learner performance, this study concentrated on 20 male and 20 female university English majors’ fluency, complexity and accuracy. Spoken protocols as samples of their task-prompted monologic speech addressed to the same male and female teacher were transcribed and coded for each of the three variables. Results of 2×2 (i.e. teacher gender × student gender) Repeated Measure Mixed Factorial ANOVA indicated a) overall higher fluency when addressing the female teacher, b) no significant differences in complexity in terms of neither the teacher nor the participant gender, c) females’ higher accuracy regardless of the addressee, d) overall higher accuracy with the male teacher, and finally, and e) significantly higher accuracy in female participants’ speech addressed to the male teacher than in any other participant-teacher pair. Implications of the study are discussed in the light of earlier findings as well as theoretical perspectives in literature.