Newly synthesized proteins have an intrinsic signal sequence, functioning as “address tags” or “zip codes”, that is essential for guiding them wherever they are needed. Owing to such a unique function, protein signals have become a crucial tool in finding new drugs or reprogramming cells for gene therapy. However, to effectively use protein signals as a desirable vehicle in the field of proteomics, the first important thing is to find a fast and powerful method to identify the “address tag” or “zip code” entity. Although all signal sequences contain a hydrophobic core region, they show great variation in both overall length and amino acid sequence. It is this variation that makes it possible to deliver thousands of proteins to many different cellular locations by varieties of modes. It is also this variation that makes it very difficult to formulate a general algorithm to predict signal sequences. Nevertheless, various prediction models and algorithms have been developed during the past 17 years. This Review summarizes the development in this area, from the pioneering methods to neural network approaches, and to the sub-site coupling approaches. Meanwhile, the future challenges in this area, as well as some promising avenues for further improving the prediction quality, have been briefly addressed as well.