Size-selective harvesting is assumed to alter life histories of exploited fish populations, thereby negatively affecting population productivity, recovery, and yield. However, demonstrating that fisheries-induced phenotypic changes in the wild are at least partly genetically determined has proved notoriously difficult. Moreover, the population-level consequences of fisheries-induced evolution are still being controversially discussed. Using an experimental approach, we found that five generations of size-selective harvesting altered the life histories and behavior, but not the metabolic rate, of wild-origin zebrafish (Danio rerio). Fish adapted to high positively size selective fishing pressure invested more in reproduction, reached a smaller adult body size, and were less explorative and bold. Phenotypic changes seemed subtle but were accompanied by genetic changes in functional loci. Thus, our results provided unambiguous evidence for rapid, harvest-induced phenotypic and evolutionary change when harvesting is intensive and size selective. According to a life-history model, the observed life-history changes elevated population growth rate in harvested conditions, but slowed population recovery under a simulated moratorium. Hence, the evolutionary legacy of size-selective harvesting includes populations that are productive under exploited conditions, but selectively disadvantaged to cope with natural selection pressures that often favor large body size.