The relationship between genotype and phenotype, the genotype-phenotype map (GPM), not only describes the genetic and molecular underpinnings of phenotypes, but also determines their variational properties. That is, it determines how genetic variation maps to phenotypic variation. Because of this, the phenotypic consequence of a random mutation may be highly constrained by properties of the GPM. Motivated by the challenge of understanding the GPM and its effect on the course of evolutionary change I here use a bacterial model to investigate how the GPM itself evolved throughout a previously conducted experiment that selected for lineages adept at cycling between the gain and loss of a simple phenotype. The Wrinkly Spreader (WS) morphotype of Pseudomonas fluorescens SBW25 is distinguished from the ancestral type by overproduction of an extracellular cellulose polymer that gives it a wrinkled colony morphology and allows it to colonise the liquid surface of a broth-filled vial, a niche unavailable to the ancestral type. The genes underpinning WS have been previously identified allowing the GPM to be characterized. This formed the basis by which I could compare the GPM of those WS derived from the selection experiment and so determine what changes had occurred throughout the extensive cycling of gain and loss of WS. Suppressor analysis of the derived WS types revealed in some cases a striking difference from the ancestral WS state, including one example of a significant re-wiring of regulatory connections and an expansion of the network of genes underpinning WS. In another case a novel association with a gene encoding a fatty acid desaturase was revealed with possible implications for an unusual switching mechanism. In some derived WS the GPM remained apparently unchanged but these WS were also implicated in switching strategies. By repeatedly re-evolving the same phenotype the GPM is required to find new viable configurations and I show in this thesis that the capacity to do so is vast.