Even though new infrastructure is being developed to meet demand, increased urbanization and vehicle ownership have increased the congestion levels in Indian cities. Attracting more travelers to public transport is an option to reduce congestion but still remains a challenge, mainly because of the uncertainty of service. A reliable and accurate system for predicting vehicle arrival can help make public transportation more attractive. An accurate prediction method should be used to provide reliable information to passengers, and accuracy depends on the input data used. Therefore, identifying the optimum inputs and incorporating them in the prediction method become important. The optimum number of inputs required for best prediction performance was identified with an analytical approach. A model-based algorithm motivated by the Kalman filter was used to predict bus travel time with the use of GPS data. A case study was conducted on two selected bus routes in the city of Chennai, India, to evaluate the prediction accuracy of the proposed method. Results obtained from the algorithm were promising and showed the prediction accuracy to be ±5 min for a prediction window of 30 min in 92% of instances. The predicted travel time can be used to provide realtime bus arrival information to the public through various media, including web pages, mobile applications, and display boards.