Individuals display consistent differences in behaviour, often described as personality, which may influence cognition. We evaluated the relationship between personality and learning in Florida scrub-jays (Aphelocoma coerulescens) and examined whether learning varied with stress physiology. Blood was collected from nestlings at 11 days post-hatch for corticosterone (CORT) assays. First, as a measure of personality, we presented scrub-jays of 8-10 months of age with a novel object to assess levels of neophobia. Second, we conducted learning tests on the same individuals in captivity. Learning tests included a colour-based association task, followed by a reversal of the award contingency. The reversal portion of the test was used to assess behavioural flexibility, which is the capability of an individual to adjust their behaviour to changes in their environment. Performance on the associative learning task was inversely related to performance on the reversal learning task. Also, bold individuals performed better on the colour-association learning task, whereas timid birds showed greater flexibility on the reversal learning task. Further, individuals with low levels of CORT as nestlings performed better on associative learning tests and worse on reversal learning tests, compared to individuals exposed to high levels of CORT. Our results indicate that scrub-jays experience a trade-off between learning and flexibility which is linked to personality, and may be mediated by early exposure to CORT. Our findings support the idea that differences in learning performance may be attributable to variations in cognitive style.