For effective foraging, many insect pollinators rely on the ability to learn and recall floral odours, behaviours that are associated with a complex suite of cellular processes. Here, we investigated how acute exposure to a high-dose of diesel exhaust (containing 19.8 and 17.5 ppm of NO and NO2, respectively) affected associative learning behaviour of honey bees (Apis mellifera) and expression of a ubiquitous heat shock protein, HSP70, in their central nervous system (CNS). To determine whether exposure to diesel exhaust would alter their tolerance to a subsequent abiotic stress, we further subjected individuals to heat stress. Diesel exhaust exposure decreased honey bees’ ability to learn and recall a conditioned odour stimulus. Whilst there was no significant difference in CNS HSP70 expression between honey bees exposed to either diesel exhaust or clean air across the entire duration of the experiment (3.5 h), there was a significant effect of time and a significant interaction between exposure treatment and time. This interaction was investigated using correlation analyses, which demonstrated that only in the diesel exhaust exposed honey bees was there a significant positive correlation between HSP70 expression and time. Furthermore, there was a 44% reduction in honey bee individuals that were able to recall the odour 72 h after diesel exposure compared with clean air control individuals. Moreover, diesel exhaust affected A. mellifera in a way that reduced their ability to survive a second subsequent stressor. Such negative effects of air pollution on learning, recall, and stress tolerance has potential to reduce foraging efficiency and pollination success of individual honey bees.