In this paper we present a method for modelling uncertainty of train delays based on a Markov stochastic process. The dynamics of a train delay over time and space is presented as a stochastic process that describes the evolution of the time-dependent random variable. Probability distribution of an arrival delay in a station changes over time in discrete steps as more information becomes available. We consider and compare the results and computational requirements of two discrete state space formulations. Moreover, we test the applicability of modelling train delays as a non-stationary Markov chain, meaning that the probability of a state change depends on the moment of transition. The model is applied on a set of historical traffic realisation data from the part of the high-speed corridor between Beijing and Shanghai. We analyse the accuracy of predictions as well as the evolution of probability distributions of all events over time. The presented method is important for making better predictions for train traffic, that are not only based on static, offline collected data, but are able to positively include the dynamic characteristics of the ever-changing delays, thus increasing the reliability of prediction by 71%.