Wild type apomyoglobin folds in at least two steps: The ABGH core rapidly, followed much later by the heme-binding CDEF core. We hypothesize that the evolved heme-binding function of the CDEF core frustrates its folding: it has a smaller contact order and is no more complex topologically than ABGH, and thus it should be able to fold faster. Therefore filling up the empty heme cavity of apomyoglobin with larger, hydrophobic side chains should significantly stabilize the protein and increase its folding rate. Molecular dynamics simulations allowed us to design four different mutants with bulkier side chains that increase the native bias of the CDEF region. In vitro thermal denaturation shows that the mutations increase folding stability and bring the protein closer to two-state behavior, as judged by the difference of fluorescence- and circular dichroism-detected protein stability. Millisecond stopped flow measurements of the mutants exhibit refolding kinetics that are over four times faster than the wild-type's. We propose that myoglobin folds not evolved to bind heme are equally stable, and find an example. Our results illustrate how the evolution of function can force proteins to adapt frustrated folding mechanisms, despite having simple topologies.