Cocaine esterase (CocE) has been known as the most efficient native enzyme for metabolizing naturally occurring cocaine. A major obstacle to the clinical application of CocE is the thermoinstability of native CocE with a half-life of only ∼11 min at physiological temperature (37 °C). It is highly desirable to develop a thermostable mutant of CocE for therapeutic treatment of cocaine overdose and addiction. To establish a structure–thermostability relationship, we carried out molecular dynamics (MD) simulations at 400 K on wild-type CocE and previously known thermostable mutants, demonstrating that the thermostability of the active form of the enzyme correlates with the fluctuation (characterized as the root-mean square deviation and root-mean square fluctuation of atomic positions) of the catalytic residues (Y44, S117, Y118, H287, and D259) in the simulated enzyme. In light of the structure–thermostability correlation, further computational modelling including MD simulations at 400 K predicted that the active site structure of the L169K mutant should be more thermostable. The prediction has been confirmed by wet experimental tests showing that the active form of the L169K mutant had a half-life of 570 min at 37 °C, which is significantly longer than those of the wild-type and previously known thermostable mutants. The encouraging outcome suggests that the high-temperature MD simulations and the structure–thermostability relationship may be considered as a valuable tool for the computational design of thermostable mutants of an enzyme.