In research on task-based learning and teaching, it has traditionally been assumed that differing degrees of cognitive task complexity can be inferred through task design and/or observations of differing qualities in linguistic production elicited by second language (L2) communication tasks. Without validating this assumption, however, it is unclear at best whether the designed or inferred difference in complexity, the key independent variable, is realized as intended. Accordingly, this study adopted diverse methods from cognitive psychology for independently measuring cognitive task complexity, including: dual-task methodology, time estimation, and self-rating. Fifty-three English-L2 speakers in Japan, representing distinct proficiency levels, narrated 4 picture sequences, each containing differing numbers of characters. While performing the primary story-telling task, participants simultaneously completed a secondary task of reacting to a color change. After each story-telling, they also estimated their time-on-task and rated their perceptions of task difficulty and mental effort. Results revealed that only large differences in the task design feature (i.e., number of elements) were detectable in terms of independent measures of cognitive complexity. This finding underscores the importance of validating the assumptions about the relationship between task design and its putative effects on cognitive complexity. Findings also indicated a potential interaction among proficiency, task designs, and measures of cognitive load.