Adaptive phenotypic plasticity is a potent but not ubiquitous solution to environmental heterogeneity, driving interest in what factors promote and limit its evolution. Here a novel computational model representing stochastic information flow in development is used to explore evolution from a constitutive phenotype to an adaptively plastic response. Results show that populations tend to evolve robustness to developmental stochasticity, but this evolved robustness limits evolvability; specifically, robust genotypes have less ability to evolve adaptive plasticity when presented with a mix of both the ancestral environment and a new environment. Analytic calculations and computational experiments confirm that this constraint occurs when the initial mutational steps toward plasticity are pleiotropic, such that mutant fitnesses decline in the environment to which their parents are well-adapted. Greater phenotypic variability improves evolvability in the model by lessening this decline as well as improving the fitness of partial adaptations to the new environment. By making initial plastic mutations more palatable to natural selection, phenotypic variability can increase the evolvability of an innovative, plastic response without improving evolvability to simpler challenges such as a shifted optimum in a single environment. Populations that evolved robustness by negative feedback between the trait and its rate of change show a particularly strong constraining effect on the evolvability of plasticity, revealing another mechanism by which evolutionary history can limit later innovation. These results document a novel mechanism by which weakening selection could actually stimulate the evolution of a major innovation.