Life at all scales is surprisingly effective at exploiting new opportunities, as demonstrated by the rapid emergence of antimicrobial resistance and novel pathogens. How populations acquire this level of evolvability and the various ways it aids survival are major open questions with direct implications for human health. Here, we use digital evolution to show that changing environments facilitate the simultaneous evolution of high mutation rates and a distribution of mutational effects skewed toward beneficial phenotypes. The evolved mutational neighborhoods allow rapid adaptation to previously encountered environments, whereas higher mutation rates aid adaptation to completely new environmental conditions. By precisely tracking evolving lineages and the phenotypes of their mutants, we show that evolving populations localize on phenotypic boundaries between distinct regions of genotype space. Our results demonstrate how evolution shapes multiple determinants of evolvability concurrently, fine-tuning a population's adaptive responses to unpredictable or recurrent environmental shifts.