Engineering thermostable proteins is advantageous for industrial and biomedical applications, where improved thermal stability can enhance conformational integrity, prolong functional half-life, and increase catalytic efficiency at elevated temperatures. We explored modifying the length of buried hydrocarbon chains to improve protein thermal stability. By optimizing the hydrophobic core through targeted amino acid substitutions, we aimed to minimize internal voids and improve core packing. To achieve this, we developed an algorithm that replaces buried hydrophobic residues with longer or bulkier hydrophobic side chains. The algorithm calculates the free energy of unfolding (ΔG) for each substitution, selecting only significantly stabilizing configurations. Functionally important residues and contact networks were excluded from mutation to preserve protein function. We applied the method to several proteins from the beta-grasp fold family. For experimental validation, we chose NEDD8, a beta-grasp protein with poor solubility and low thermal stability. Two subtle substitutions predicted by our algorithm increased NEDD8's thermal stability by 1.7 kcal/mol and raised its melting point by 17°C. MD simulations and NMR spectroscopy revealed reduced conformational fluctuations and increased stabilizing interactions, such as hydrogen bonding and electrostatic contacts. Functional assays confirmed that the substitutions did not perturb NEDD8's global fold or interactions with cofactors and enzymes. These results highlight the effectiveness of tuning buried hydrophobic residues to enhance protein stability without compromising function. This strategy could serve as a general framework for designing robust therapeutic proteins and enzymes for industrial or biomedical applications.