Why do some people perform a task better than others? Influential theories of skill acquisition and expertise suggest that cognitive determinants of performance vary as a function of practice and task features. Previous research identified consistent stimulus-response mappings as a primary determinant of whether a task can become automatic (Fitts & Posner, 1967). This theory has held for simple tasks where fluid abilities become less predictive of performance over time (Ackerman & Woltz, Journal of Educational Psychology,86, 487–515, 1994). However, for more complex tasks, fluid abilities continue to predict performance despite training (Ackerman & Cianciolo, Journal of Experimental Psychology: Applied, 8, 194–208, 2002). In a large sample of university and community participants (N = 818), we extend previous research by using an extensive cognitive ability battery and a novel complex learning task that allows us to manipulate stimulus-response consistency while also controlling other task features. Using multigroup structural equation modeling, we demonstrate that while variable-mapping impairs performance, the performance-ability relationships in this complex task remain unchanged. Variable mapping did not alter which cognitive abilities were required by the task initially or following practice. Performance on both consistently and variably mapped versions was best predicted by fluid intelligence, whereas completion time was predicted by both fluid intelligence (higher = slower) and processing speed (higher = faster). Viewed in the context of prior literature, these findings suggest that complexity can override the benefits of consistency, maintaining the influence of cognitive abilities despite practice.