Over the recent years, growing number of studies suggests that intensive size-selective fishing can cause evolutionary changes in life-history traits in the harvested population, which can have drastic negative effects on populations, ecosystems and fisheries. However, most studies to date have overlooked the potential role of immigration of fish with different phenotypes as an alternative plausible mechanism behind observed phenotypic trends. Here, we investigated the evolutionary consequences of intensive fishing simultaneously at phenotypic and molecular level in Eurasian perch (Perca fluviatilis L.) population in the Baltic Sea over a 24-year period. We detected marked changes in size- and age-distributions and increase in juvenile growth rate. We also observed reduction of age at sexual maturity in males that has frequently been considered to support the hypothesis of fisheries-induced evolution. However, combined individual-based life-history and genetic analyses indicated increased immigration of foreign individuals with different life-history patterns as an alternative mechanism behind the observed phenotypic change. This study demonstrates the value of combining genetic and phenotypic analyses and suggests that replacement or breakdown of locally adapted gene complexes may play important role in impeding the recovery of fish populations.