The history of life is a history of evolutionary innovations, qualitatively new phenotypic traits that endow their bearers with new, often game-changing abilities. We know many individual examples of innovations and their natural history, but we know little about the fundamental principles of phenotypic variability that permit new phenotypes to arise. Most phenotypic innovations result from changes in three classes of systems: metabolic networks, regulatory circuits, and macromolecules. I here highlight two important features that these classes of systems share. The first is the ubiquity of vast genotype networks - connected sets of genotypes with the same phenotype. The second is the great phenotypic diversity of small neighborhoods around different genotypes in genotype space. I here explain that both features are essential for the phenotypic variability that can bring forth qualitatively new phenotypes. Both features emerge from a common cause, the robustness of phenotypes to perturbations, whose origins are linked to life in changing environments.