Colorado potato beetle is a key worldwide pest of potato crops. It has repeatedly developed resistance to insecticides; thus, its management requires alternative strategies that incorporate cultural and biological controls. Our ability to develop effective control methods requires a better understanding of its ecology and behavior. Previous work identified a male-produced aggregation pheromone that is attractive to adult males and females, and even to larvae. Other work has found evidence of a yet-unidentified female-produced pheromone. However, this potential two-way pheromone communication system, and its implications for pest management, are not well-studied. Here we investigated whether male mate-finding behavior was altered based on previous exposure of potato plants to female, male, or no adults. We found that in no-choice tests, virgin males walked for a longer time, undertook more transitions between walking and stopping with antennae up, visited more leaves, and departed more slowly from female-exposed plants than from male-exposed or unexposed plants. When presented leaves from female-exposed, male-exposed, and unexposed plants simultaneously in a three-way choice test, virgin males exhibited behavior consistent with that in no-choice tests, with virgin males spending more time and exhibiting more mate-seeking behaviors on female-exposed than on male-exposed or unexposed plants. These results indicate a male preference for plants containing female-specific residues, providing insight into semiochemically-mediated attraction and retention of male beetles on potato plants. This knowledge, in concert with further work on pheromone identification and synthesis, can be used to develop new sustainable Colorado potato beetle management strategies that integrate cultural and behavioral controls.