As cryptocurrency is widely accepted and used, illegal activities based on it have also attracted attention, especially phishing scams, which bring great losses to both customers and countries. Therefore, early-stage detection of this behavior is of great significance, as it can minimize users’ losses when a phishing scam is ongoing. Existing detection methods perform effectively with all available data; however, in the early stage of a phishing scam, the performance is not satisfactory. This paper proposes the Early-stage Phishing Detection framework, which contains data processing, feature extraction, and detection components. One main contribution of this paper is the design of features based on the local graph structure and time-series attributes of the transaction network. Moreover, the phishing scam is divided into early, middle, and late stages, according to the fraud amount. Finally, the proposed method is validated on a real dataset, and the experimental results show that it can achieve the best performance. Specifically, in the early stage, the proposed method performs far better than the embedding methods. In addition, with time, it can maintain a certain degree of robustness. Thus, this paper provides useful ideas for regulators and platforms to detect phishing scams in advance.