The present study aimed for better understanding of the interactions between task complexity and students' self-efficacy beliefs and students' use of learning strategies, and finally their interacting effects on task performance. This investigation was carried out in the context of Chinese students learning English as a foreign language in a university in China. The participants were 78 second-year university students (mean age = 20.9 years). This study used a repeated-measures design with task complexity as the within-participants factor, and task sequence as the between-participants factor. Results indicated a significant task effect for self-efficacy beliefs and task performance, and a significant interaction effect of sequence with task complexity for learners' self-efficacy beliefs in learning for both task versions, learners with higher self-efficacy beliefs had better task performances than learners with lower self-efficacy beliefs. The results also revealed a strong correlation between self-efficacy and the use of learning strategies for both tasks.