Accurate bus travel time information helps passengers plan their trips more effectively and can potentially increase ridership. However, cyclical factors (e.g., time of day, weather conditions, holidays), unpredictable factors, and other complex factors (e.g., dynamic traffic conditions, dwell times, variations in travel demand) make accurate bus travel time prediction challenging. This study aims to improve travel time prediction accuracy. To achieve this, we developed a bus travel time prediction framework based on similar historical Global Positioning System (GPS) trajectory data and an information decay technique. The framework first divides the predicted bus route into segments, integrating GPS trajectory data with road map processing techniques to accurately map the bus’s position and estimate its arrival time at bus stops. Then, instead of relying on a single historical trajectory that best matches the predicted bus journey, the framework samples a set of similar trajectories as the basis for travel time estimation. Finally, the information decay technique is applied to construct a bus travel time prediction interval. We conduct comprehensive experiments using GPS trajectory data collected from Kandy, Sri Lanka, and Ho Chi Minh City, Vietnam, to validate our ideas and evaluate the proposed framework. The experimental results show that the proposed prediction framework significantly improves accuracy compared to baseline approaches by considering factors such as bus stops, time of day, and day of week.