This paper proposes a methodology for online prediction of travel time reliability based on real-world measurements in light of the probabilistic character of traffic breakdown. A discrete time Markov chain is developed to represent the flow breakdown event. Through the calibrated transition probability matrix of the Markov chain, the probability of flow breakdown or recovery along a given facility can be estimated. Travel time reliability that captures the probability of flow breakdown and the conditional expected delay associated with occurrence of breakdown can therefore be predicted. Because both the mean and the variance of travel time are represented as functions of current traffic conditions and calibrated for each road section on the basis of field data, travel time and its reliability could be obtained offline by analyzing historical data and computed online when real-time measurements are available.