This study presents a methodology for travel-time prediction on urban arterial networks using data from global positioning system (GPS) probe vehicles, under Indian traffic conditions. Given any link in the network, the model predicts its travel time on the basis of historic patterns and real-time information. By doing this, it would be possible to find the time required to travel on all possible routes for any given origin-destination pair. The study also emphasizes the need for splitting links into intersection and midlinks. The k-nearest neighbor algorithm was used for prediction at the midlinks and a random forest predictor was developed to predict the travel time on the high-variation intersection links. For intersections with location-based sensors, a methodology for delay and travel-time prediction was proposed on the basis of predicted values of queue length. Overall, it was observed that better prediction accuracy was achieved when links were considered separately as midlink and intersection. The model was validated on a study network using GPS data procured from public transport buses in Chennai, India. © 2016 American Society of Civil Engineers.