Genetic adaptation and phenotypic plasticity are two ways in which organisms can adapt to local environmental conditions. We examined genetic and plastic variation in gill and brain size among swamp (low oxygen; hypoxic) and river (normal oxygen; normoxic) populations of an African cichlid fish, Pseudocrenilabrus multicolor victoriae. Larger gills and smaller brains should be advantageous when oxygen is low, and we hypothesized that the relative contribution of local genetic adaptation versus phenotypic plasticity should be related to potential for dispersal between environments (due to gene flow's constraint on local genetic adaptation). We conducted a laboratory-rearing experiment, with broods from multiple populations raised under high- and low-oxygen conditions. We found that most of the variation in gill size was due to plasticity. However, both plastic and genetic effects on brain mass were detected, as were genetic effects on brain mass plasticity. F1 offspring from populations with the highest potential for dispersal between environments had characteristically smaller and more plastic brains. This phenotypic pattern might be adaptive in the face of gene flow, if smaller brains and increased plasticity confer higher average fitness across environment types.