A sample of 203 task naïve left- and right-handed participants were asked to complete a combination of the 3- and 4-disk Towers of Hanoi (ToH), manipulating novelty and complexity. Self-reported state anxiety and latency to respond (initiation time) were recorded before each ToH. Novelty had a major effect on initiation time, particularly for left-handers. Left-handers had a longer latency to start and this was significantly longer on the first trial. Irrespective of hand-preference, initiation time reduced on the second trial, however, this was greatest for left-handers. Condition of task did not systematically influence initiation time for right handers, but did for left-handers. State anxiety was influenced by task novelty and complexity in a more complicated way. During the first trial, there was a significant handedness × number of disks interaction with left-handers having significantly higher state anxiety levels before the 3-disk ToH. This suggests that the initial reaction to this task for left-handers was not simply due to perceived difficulty. On their second trial, participants completing a novel ToH had higher state anxiety scores than those completing a repeated version. Overall, left-handers had a larger reduction in their state anxiety across trials. Relating to this, the expected strong positive correlation between state and trait anxiety was absent for left-handed females in their first tower presentation, but appeared on their second. This was driven by low trait anxiety individuals showing a higher state anxiety response in the first (novel) trial, supporting the idea that left-handed females respond to novelty in a way that is not directly a consequence of their trait anxiety. A possible explanation may be stereotype threat influencing the behavior of left-handed females.