With the rapid development of marine IoT (Internet of Things), ocean MDTN (Mobile Delay Tolerant Network) has become a research hot spot. Long-term trajectory prediction is a key issue in MDTN. There are no long-term fine-grained trajectory prediction methods proposed for ocean vessels because a vessel’s mobility pattern lacks map topology support and can be easily influenced by the fish moratorium, sunshine duration, etc. A traditional on-land trajectory prediction algorithm cannot be directly utilized in this field because trajectory characteristics of ocean vessels are far different from that on land. To address the problem above, we propose a novel long-term trajectory prediction algorithm for ocean vessels, called L-VTP, by utilizing multiple sailing related parameters and K-order multivariate Markov Chain. L-VTP utilizes multiple sailing related parameters to build multiple state-transition matrices for trajectory prediction based on quantitative uncertainty analysis of trajectories. Trajectories’ sparsity of ocean vessels results in a critical state missing problem of a high-order state-transition matrix. L-VTP automatically traverses other matrices in a specific sequence in terms of quantitative uncertainty results to overcome this problem. Furthermore, the different mobility models of the same vessel during the day and the night are also exploited to improve the prediction accuracy. Privacy issues have been taken into consideration in this paper. A quantitative model considering Markov order, training metadata and privacy leak degree is proposed to help the participant make the trade-off based on their customized requirements. We have performed extensive experiments on two years of real-world trajectory data that include more than two thousand vessels. The experiment results demonstrate that L-VTP can realize fine-grained long-term trajectory prediction with the consideration of privacy issues. The average error of 4.5-hour fine-grained prediction is less than 500 m. In addition, the proposed method can be extended to 10-hour prediction with an average error of 2.16 km, which is also far less than the communication range of ocean vessel communication devices.