Travel time information is generally nonlinear and nonstationary in a dynamic environment, and therefore no consistent tendency can be easily observed. This research developed a novel approach that combined the empirical decomposition method for speed data analysis and gray theory for travel time prediction to predict the arrival time at each stop along a bus route. In addition, sensitivity analysis was performed for different numbers of stops. With an average prediction error of less than 3.5%, the experiments showed that the proposed prediction approach, which employed both historical and real-time speed data collected from the geographic positioning system, outperformed Chou’s approach, which used only historical speed data. The proposed prediction method could be readily incorporated into a cell phone–based information retrieval system that indicated bus position en route as well as its arrival times at all stops.