Protein methylation catalyzed by methyltransferases carries many important biological functions. Methylation and their regulatory enzymes are involved in a variety of human disease states, raising the possibility that abnormally methylated proteins can be disease markers and methyltransferases are potential therapeutic targets. Identification of methylation sites is a prerequisite for decoding methylation regulatory networks in living cells and understanding their physiological roles that have been implicated in the pathological processes. Due to various limitations of experimental methods, in silico approaches for identifying novel methylation sites have become increasingly popular. In this review, we summarize the progress in the prediction of protein methylation sites from the dataset, feature representation, prediction algorithm and online resources in the past ten years. We also discuss the challenges that are faced while developing novel predictors in the future. The development and application of methylation site prediction is a promising field of systematic biology, provided that protein methyltransferases, species and functional information will be taken into account.