Quantitative genetics theory predicts adaptive evolution to be constrained along evolutionary lines of least resistance. In theory, hybridization and subsequent interspecific gene flow may, however, rapidly change the evolutionary constraints of a population and eventually change its evolutionary potential, but empirical evidence is still scarce. Using closely related species pairs of Lake Victoria cichlids sampled from four different islands with different levels of interspecific gene flow, we tested for potential effects of introgressive hybridization on phenotypic evolution in wild populations. We found that these effects differed among our study species. Constraints measured as the eccentricity of phenotypic variance-covariance matrices declined significantly with increasing gene flow in the less abundant species for matrices that have a diverged line of least resistance. In contrast, we find no such decline for the more abundant species. Overall our results suggest that hybridization can change the underlying phenotypic variance-covariance matrix, potentially increasing the adaptive potential of such populations.