Recent findings have shown that language plays an important role in the acquisition of novel cognitive tasks (van 't Wout & Jarrold, 2020). The current study sought to elucidate the factors that influence the contribution of language to novel task learning, focusing specifically on the role of task complexity (defined by the number of stimulus-response [S-R] rules per task) and the role of task instructions (by comparing trial-and-error learning to instruction-based learning). In each experiment participants were required to learn the correct response to novel sets of picture stimuli. When analyzed as a function of stimulus occurrence within a task, both experiments found that initial performance was worse under articulatory suppression (AS; verbal distractor task) than under foot tapping (i.e., nonverbal distractor task), but only if the task was more complex (consisting of 6S-R rules) and not if it was less complex (consisting of three or four S-R rules), suggesting that the acquisition of a simpler task by trial and error might not require verbal mediation. Experiment 2 furthermore found that the role of language was modulated by the manner of acquisition: For trial-and-error learning, the detrimental effect of AS increased and then decreased again as a function of stimulus occurrence. Conversely, for instruction-based learning, AS exclusively affected the first few stimulus occurrences, suggesting that participants can create a verbal representation of the task during the instruction phase. Together, these experiments demonstrate that the role of language in novel task learning is modulated by task complexity and task instructions.