We studied the ability of honeybees to discriminate between single odorants and binary olfactory mixtures. We analyzed the effect of the number of common elements between these two stimulus classes on olfactory discrimination. We used olfactory conditioning of the honeybees' proboscis extension reflex (PER), a paradigm in which odors can be associated with a reinforcement of sucrose solution. Bees were asked to discriminate reinforced from nonreinforced olfactory stimuli. They were trained with two elemental odors (A and B) versus a binary olfactory mixture. The mixture was either AB (group 2CE, two common elements), AC (group 1CE, one common element A), or CD (group 0CE, no common element). Three groups followed a positive patterning schedule (mixture reinforced and elements nonreinforced: groups 2CE+, 1CE+, and 0CE+) and three other groups a negative patterning schedule (mixture nonreinforced and elements reinforced: groups 2CE−, 1CE−, and 0CE−). We showed that a reduction of similarity (number of common elements) between elemental odors and compounds enhanced the ability to discriminate elements from compounds and that the kind of compound processing used by the bees supports theories that assume nonelemental compound processing (i.e., that exclude the mere summation of the elemental associative strengths upon compound presentation).