Over the last years the number of AIS messages generated by ships to signal their position has been increasing thus permitting decision support systems to build new strategies based on the elaboration of such data. In this paper we propose an algorithm based on a K-Nearest Neighbor classifier to predict ships routes. The algorithm was tested on real data extracted from AIS messages collected around Malta. Experiments show that our algorithm reaches a precision of 0.794, a recall of 0.785 and an accuracy of 0.931.