Abstract: Bus travel time between stops has obvious period distribution characteristics .The buses ,with the char-acteristic of state transition ,have a typical space-time process .In order to predict the bus travel time between stops in the future period of time accurately ,an improved algorithm based on the basic Markov chain is proposed .The algorithm can be divided into two steps .The first step is to set up the first-order Markov transition matrix for a specific bus route dur-ing different period of time with the bus GPS data and then to predict the bus travel time between stops based on the ma-trix .The second step is to improve the basic Markov chain algorithm by leading up the compensation of moving error . The algorithm was tested and validated by using the data taken from the bus route B1 of Guangzhou BRT .The test result shows that the improved algorithm with the compensation of moving error provides better predicting accuracy than both basic Markov chain algorithm and the BP neural network algorithm and that the improved algorithm is simple in imple-mentation .