The parasitoid Binodoxys communis is a candidate for release against the Asian soybean aphid, Aphis glycines in North America. We investigated responses of B. communis to volatiles from target and non-target host-plant complexes using a series of Y-tube olfactometer assays. The non-target host plant complexes included 3 native aphid species and one species presumed to be exotic. We assessed responsiveness to, and preference for, odors from either target or non-target host plant complexes for parasitoids with oviposition experience on different aphid-plant combinations. We also determined if the parasitoid distinguishes between volatiles from soybean plants infested with A. glycines versus those from uninfested plants. Volatiles from the A. glycines host plant complex and several non-target host plant complexes elicited a response in B. communis, which was altered or reinforced through oviposition experience. In general, wasps with experience on a specific host plant complex increased their responsiveness to odors of this complex. Although naïve wasps were not attracted to soybean aphid host plant complex odors, volatiles from one non-target host plant complex did elicit an innate response. However, naïve wasps and those experienced on target or non-target host plant complexes did not prefer odors from either complex. Our data also indicate that B. communis is unable to distinguish between volatiles from infested vs. uninfested soybean plants. We show that B. communis is responsive to a broad array of olfactory stimuli, exhibits low fidelity for any particular odor and employs a high degree of behavioral plasticity in its response to volatile cues.