Evolutionary change is considered a major factor influencing the invasion of new habitats by plants. Yet, evidence on how such modifications promote range expansion remains rather limited. Here we investigated flower color modifications in the red poppy, Papaver rhoeas (Papaveraceae), as a result of its introduction into Central Europe and the impact of those modifications on its interactions with pollinators. We found that while flowers of Eastern Mediterranean poppies reflect exclusively in the red part of the spectrum, those of Central European poppies reflect both red and ultraviolet (UV) light. This change coincides with a shift from pollination by glaphyrid beetles (Glaphyridae) to bees. Glaphyrids have red-sensitive photoreceptors that are absent in bees, which therefore will not be attracted by colors of exclusively red-reflecting flowers. However, UV-reflecting flowers are easily detectable by bees, as revealed by visual modeling. In the North Mediterranean, flowers with low and high UV reflectance occur sympatrically. We hypothesize that Central European populations of P. rhoeas were initially polymorphic with respect to their flower color and that UV reflection drove a shift in the pollination system of P. rhoeas that facilitated its spread across Europe.