Volatile organic compounds (VOCs) serve as important infochemicals, mediating several ecological interactions including herbivory and pollination. Atmospheric pollutants including traffic-related air pollution may impair the detection of VOCs used by insects in insect-plant interactions. We investigated the indirect effect of petrol exhaust pollution on olfactory learning and memory (short and long term) in honey bees. Using appetitive olfactory conditioning, we trained bees to learn one of four floral VOC profiles; linalool, dipentene, myrcene and geranium. VOCs were unpolluted or polluted with exhaust collected from a petrol generator. Exhaust emissions included concentrations of CO (246.07 + 17 ppm), NO (20.50 + 6.90 ppb) and NO2 (20.93 + 0.05 ppb) consistent with those typically encountered in urban areas and near roads. Once bees had learnt the training VOC, we tested whether they could recognise that VOC 1 hour, 24 hours and 48 hours post-training. Bees took significantly longer to learn polluted VOCs and forgot them faster than unpolluted ones. We also tested the ‘masking’ potential of pollution on floral VOCs. Using Gas Chromatography Mass Spectroscopy we noted differences in the chemical profile of polluted versus unpolluted VOCs and tested whether bees could recognise polluted VOCs if trained using unpolluted ones. For several VOCs tested, bees could distinguish between polluted and unpolluted VOCs. Ultimately, our results show that air pollution changes the recognition and retention of floral VOCs by bees which may consequently impact foraging efficiency.