Several computational methods have been developed to solve the problem of protein thermostabilization. One common drawback of them is that they must have the information of a backbone structure of a protein for the generation of a proper amino acid sequence. In this paper, we propose a new method called TargetStar by incorporating computational biology and statistical physics, in which an approximate partition function and a specific heat are used to calculate the folding transition temperature of a protein and then to predict the relative thermal stabilities for given proteins based only on their amino acid sequences. To evaluate the prediction accuracy of TargetStar, we calculated folding transition temperatures of 289 orthologous protein pairs using the proposed method, where each protein pair contains one hyperthermophilic protein and one mesophilic protein. According to our evaluation, hyperthermophilic and mesophilic proteins are distinguished from each other in terms of relative thermal stabilities with 77% prediction accuracy. Thus, TargetStar may serve as an efficient method to design an amino acid sequence of a target protein with the desired thermal stability prior to the expensive and time-consuming mutagenesis experiment.