Natural and engineered proteins have recently been discovered with a unique ability to reversibly switch between entirely different 3-dimensional structures, with accompanying major changes in their secondary structure contents, hydrophobic sidechain packing and overall shape. The major conformational changes in these shape-shifting proteins are triggered by, for example, ligand binding, changes in pH, or — as in evolutionary processes — mutations. Using a coarse-grained model for protein folding with 7 atoms per amino acid and 3 amino acid types (polar, hydrophobic and turn-type), we investigate the character of fold switching transitions. We determine the folding thermodynamics of several “single-ground state” sequences that fold spontaneously into a unique structure, including all-alpha, mixed alpha-beta, and beta barrel folds. We then apply a generalized-ensemble Monte Carlo algorithm to explore sequences that lie in the space between folds. We find that proteins in our model can be driven to switch folds through a series of mutations without needing to pass through unstable “non-folding” sequences, in line with recent protein design experiments. At the border between folds, some sequences exhibit an ability to populate more than one fold. Such sequences are relatively rare, however, and fold changes are therefore typically accomplished in just a few mutational steps. We comment on potential evolutionary implications.