Recent advances in the probe vehicle deployment offer an innovative prospect for research in arterial travel time estimation. Specifically, we focus on the estimation of probability distribution of arterial route travel time, which contains more information regarding arterial performance measurements and travel time reliability. One of the fundamental contributions of this work is the integration of travel time correlation of route's successive links within the methodology. In the proposed technique, given probe vehicles travel times of the traversing links, a two-dimensional (2D) diagram is established with data points representing travel times of a probe vehicle crossing two consecutive links. A heuristic grid clustering method is developed to cluster each 2D diagram to rectangular sub spaces (states) with regard to travel time homogeneity. By applying a Markov chain procedure, we integrate the correlation between states of 2D diagrams for successive links. We then compute the transition probabilities and link partial travel time distributions to obtain the arterial route travel time distribution. The procedure with various probe vehicle sample sizes is tested on two study sites with time dependent conditions, with field measurements and simulated data. The results are very close to the Markov chain procedure and more accurate once compared to the convolution of links travel time distributions for different levels of congestion, even for small penetration rates of probe vehicles. (C) 2012 Elsevier Ltd. All rights reserved.