Previous studies have shown inconsistent results concerning bilinguals' use of gestures to compensate for reduced proficiency in their second language (L2). These results could be because of differing task demands. In this study, we asked 16 intermediate English L2 speakers (whose first language [L1] was Chinese) to watch a story and tell it back in both languages. We attempted to link gesture use to proficiency while accounting for task complexity as measured by scenes recalled. The results showed that these L2 speakers told longer stories in their L1 and used more iconic gestures in their L2. There were also trends for the women to tell longer stories and use more gestures in their L2 compared to the men. These results are consistent with the idea that the relationship between gesture use and proficiency is mediated by task complexity. The trends for gender differences, however, point to the possibility that gesture use is also related to expressivity.