A new computer program (CORE) is described that predicts core hydrophobic sequences of predetermined target protein structures. A novel scoring function is employed, which for the first time incorporates parameters directly correlated to free energies of unfolding (ΔGu), melting temperatures (Tm), and cooperativity. Metropolis-driven simulated annealing and low-temperature Monte Carlo sampling are used to optimize this score, generating sequences predicted to yield uniquely folded, stable proteins with cooperative unfolding transitions. The hydrophobic core residues of four natural proteins were predicted using CORE with the backbone structure and solvent exposed residues as input. In the two smaller proteins tested (Gβ1, 11 core amino acids; 434 cro, 10 core amino acids), the native sequence was regenerated as well as the sequence of known thermally stable variants that exhibit cooperative denaturation transitions. Previously designed sequences of variants with lower thermal stability and weaker cooperativity were not predicted. In the two larger proteins tested (myoglobin, 32 core amino acids; methionine aminopeptidase, 63 core amino acids), sequences with corresponding side-chain conformations remarkably similar to that of native were predicted.