The presence of macrolides in food and the environment poses a substantial threat to the sustainable development of natural ecosystems and presents risks to human health. Previous research has demonstrated that microbial esterases can degrade erythromycin (Ery), roxithromycin (Rox), and clarithromycin (Clr), rendering them candidates for bioremediation of macrolide residues. However, the efficacy of esterases is limited by insufficient thermal stability, restricting their widespread application. To address this challenge, this study employed a combinatorial strategy integrating computational molecular dynamics (MD) simulations, server-assisted virtual mutation prediction, and a greedy algorithm for protein engineering to enhance the thermal stability of esterase C from Enterobacter hormaechei (Ehno-EreC). After four rounds of screening, we successfully obtained a four-point mutant, M4 (D245P/S141A/D154I/T292W), which exhibited significantly improved thermal stability compared to the wild-type enzyme. Notably, the M4 mutant not only extended the enzyme's half-life at 40 °C from 7 to 1095 min, but also increased its degradation activity against Ery, Rox, and Clr. Structural analyses revealed enhanced rigidity in the loop between the major and minor lobes and the strengthened hydrophobic interactions post-mutation, contributing to the enzyme's structural stability. This finding was consistent with the observed reduction in correlated and anti-correlated motions in the MD trajectory.