During the upsurge of the introduced predatory Nile perch in Lake Victoria in the 1980s, the zooplanktivorous Haplochromis (Yssichromis) pyrrhocephalus nearly vanished. The species recovered coincident with the intense fishing of Nile perch in the 1990s, when water clarity and dissolved oxygen levels had decreased dramatically due to increased eutrophication. In response to the hypoxic conditions, total gill surface in resurgent H. pyrrhocephalus increased by 64%. Remarkably, head length, eye length, and head volume decreased in size, whereas cheek depth increased. Reductions in eye size and depth of the rostral part of the musculus sternohyoideus, and reallocation of space between the opercular and suspensorial compartments of the head may have permitted accommodation of larger gills in a smaller head. By contrast, the musculus levator posterior, located dorsal to the gills, increased in depth. This probably reflects an adaptive response to the larger and tougher prey types in the diet of resurgent H. pyrrhocephalus. These striking morphological changes over a time span of only two decades could be the combined result of phenotypic plasticity and genetic change and may have fostered recovery of this species.