Environmental complexity influences cognitive development and may benefit group-housed calves. We hypothesized that environmental enrichment would improve success in a cognitive task. Holstein heifer calves were randomly assigned to different group pens with access to either hay (H; n = 6), a rotating brush (B; n = 6), or no additional enrichment (C; n = 5). All calves received milk replacer (8 L/d) via an automated milk feeder and grain concentrate ad libitum. At wk 5 of age, calves were tested in a T-maze with a reward (0.2 L milk). Calves were assessed first in initial spatial learning and then in reversal learning, where the reward location was changed to the opposite arm. Calves received 5 sessions/d for 5 d until they met a passing criteria (moving directly to correct side in 3 consecutive sessions) or reached a maximum of 20 sessions. We recorded the time to find the reward (completion time) for individual sessions and the total number of sessions required to pass both learning stages. Data were analyzed by stage in a generalized linear mixed model, with session as a repeated measure for completion time. All B and H calves passed initial learning and 80% (n = 4) C calves passed. Number of sessions required to pass initial learning did not differ (5.9 sessions; SE = 2.38; P = 0.52). In reversal learning, there was an effect of enrichment on number of sessions required to pass (P < 0.001), with C calves requiring more sessions than H calves (P = 0.005) and B calves having an intermediate outcome (13.0 vs. 9.83 vs. 6.83; C vs. B vs. H; SE = 1.22). Completion time did not differ between treatments during initial (50.2 s/session; SE = 18.2; P = 0.40) or reversal (75.4 s/session; SE = 21.4; P = 0.59) stages, but decreased over sessions (P < 0.001). These results suggest that environmental enrichment, particularly nutritional enrichment, may improve behavioral flexibility of group-housed calves.