Missense mutations, which are single base pair genetic alternation resulting in a different amino acid, are among the most common occurring variants in exon regions of the human genome and may lead to diseases. Thus to assess the effects of missense mutations, it is essential to investigate the evolutionary history of the protein under selection pressures. In this study, we employ a continuous-time Markov model to investigate the evolutionary patterns in protein sequences and a Bayesian Markov chain Monte Carlo method to estimate the substitution rates for protein of interest, from which we obtain scoring matrices. Specifically, we examined the evolutionary patterns of protein sequences containing missense mutations using a species tree to define the phylogeny of the protein of interest. We thoroughly studied the evolutionary pattern of human muscle glycogen phosphorylase containing 127 known missense mutations, and identified characteristic evolutionary patterns in 63 proteins with 2,238 missense mutations, including both deleterious and neutral effects. Our results show that the estimated protein-specific evolutionary pattern-based scoring matrices (PSM) lead to higher sensitivity in detecting the pathological effects of missense mutations, compared to the general evolutionary pattern-based scoring matrix of Blosum62 (BL62) matrix. By incorporating PSM, the performance of a recently released structure-based model SPRI for evaluating missense mutations is further improved.