Despite recent advances in our understanding of the importance of protein-surface properties for protein thermostability, to date many rational designs have been focused instead on protein-core characteristics such as core packing and cavity filling. Rational strategies to design protein surfaces to improve protein thermostability have not yet been well investigated. Here, an efficient rational design of a surface cavity for improving protein thermostability without reducing enzyme activity is suggested. Bacillus circulans xylanase (Bcx) was used as a model enzyme. Two structural features related to protein thermostability, protein cavities and flexibility were considered to identify thermo-labile residues. Residues with flexible motions in surface cavities were selected and redesigned for xylanase thermostabilization using a computational method to stabilize the local interactions of the surface cavities. Three thermostable single mutants (F48Y, T50V, and T147L) were experimentally identified, and combination of the single mutants resulted in a more thermostable triple mutant (F48Y/T50V/T147L). The thermostability and the catalytic efficiency of the triple mutant were 15 times and 1.3 times higher than wild-type Bcx, respectively. Our surface-cavity design strategy showed that flexible surface residues tolerant to mutations are valid targets for thermostabilization with no reduction in catalytic activity, and that local-interaction stabilization of cavity-lining residues using the computational method can be an effective alternative to the conventional cavity-filling method. This strategy can be used as a practical approach to increase protein thermostability.