•Create a database from more than 141 million AIS records.•Propose a random forest-based model to measure the similarity between trajectories.•Develop a decision strategy for vessel destination prediction. Shipping is one of the major transportation approaches around the world. With the growing demands for global shipping service, vessel destination prediction has shown its significant role in improving the efficiency of decision making in industry and ensuring a safe and efficient maritime traffic environment. Currently, most vessel destination prediction methods focus on regional destination prediction, which has restrictions on destinations and regions. Thus, this paper proposes a general AIS (Automatic Identification System) data-driven model for vessel destination prediction. In this random forest-based model, the similarity between the vessel’s traveling and historical trajectories are measured and utilized to predict the destination. The destination of the historical trajectory, which shares the highest similarity with the traveling trajectory, is predicted as the vessel’s destination. The method is different from previous work which used maritime records as input to predict the destination. In our method, a historical trajectory database was generated from more than 141 million AIS records, which covers 534,824 traveling patterns between ports and more than 5.9 million historical trajectories. Comparative studies were carried out to validate the performance of the proposed model, where eleven state-of-the-art trajectories similarity measurement methods combined with two different decision strategies were implemented and compared. The experimental results demonstrate that the proposed model combined with the port frequency-based decision strategy achieves the best prediction accuracy on 35,937 testing trajectories.