The pervasive use of synchronous computer-mediated communication (SCMC) in second language (L2) learning has generated increasing interest among researchers in integrating SCMC with task-based language teaching (TBLT). This study examined the effects of task complexity on Chinese EFL learners' language production in SCMC modality to develop optimal tasks that facilitate the learning of English in SCMC environments. Eighty-four intermediate Chinese EFL learners completed two interactive tasks (simple and complex) in dyads via text-based or video-based SCMC. Their English productions were transcribed and coded in terms of syntactic complexity, lexical complexity and accuracy for statistical analyses. The results indicated that increasing task complexity elicited significantly lower syntactic complexity in text-based SCMC, but without significant effects on syntactic complexity in video-based SCMC. Significantly higher lexical complexity and unaffected accuracy were observed in both SCMC modes as a result of an increase in task complexity. Regarding SCMC modality, text-based SCMC resulted in significantly lower syntactic complexity, but significantly higher lexical complexity and accuracy than video-based SCMC.