A method is proposed to predict the state of traffic for the near future. Traffic conditions are assumed to follow a stochastic process. A Markov model is developed to characterize the transition between traffic states. Unlike previous models in the literature, the state transition probability matrix is assumed to be a function of traffic variables; therefore, the proposed Markov model considers time-varying covariates. The base transition matrix and the effect of each covariate are calibrated to a data set for an urban expressway in Toronto, Ontario, Canada, by using maximum likelihood estimation. Using the transition probabilities of the Markov model, the proposed procedure constructs the empirical distribution of travel speed. The procedure, which can be applied in real time, uses both the empirical distribution of travel speed for different traffic conditions and the predicted transition matrix for the near future. Therefore, the proposed method enables the prediction of both the expected speed value and its distribution for the near future. Finally, a procedure is proposed to improve the prediction results of any travel time prediction method. This procedure uses a short-memory time series model by incorporating the predicted transition probabilities of the proposed Markov model. An evaluation using field data demonstrates this improvement for a simple time series model.