Cryptic invasions are commonly associated with genetic changes of the native species or genetic lineage that the invaders replace. Phenotypic shifts resulting from cryptic invasions are less commonly reported given the relative paucity of historical specimens that document such phenotypic changes. Here, I study such a case in two populations of threespine stickleback from central Europe, comparing contemporary patterns of gene flow with phenotypic changes between historical and contemporary population samples. I find gene flow from an invasive lineage to be associated with significant phenotypic changes, where the degree of phenotypic change corresponds with the level of gene flow that a population receives. These findings underline the utility of combining genetic approaches with phenotypic data to estimate the impact of gene flow in systems where anthropogenic alterations have removed former geographic barriers promoting cryptic invasions.