Predicting truck (heavy vehicle) travel time is a principal component of freight project prioritization and planning. However, most existing travel time prediction models are designed for passenger vehicles and fail to make truck specific forecasts or use truck specific data. Little is known about the impact of this limitation, or how truck travel time prediction could be improved in response to freight investments with an improved methodology. In light of this, this paper proposes a pragmatic multi-regime speed-density relationship based approach to predict freeway truck travel time using empirical truck probe GPS data (which is increasingly available in North American and Europe) and loop detector data. Traffic regimes are segmented using a cluster analysis approach. Two case studies are presented to illustrate the approach. The travel time estimates are compared with the Bureau of Public Roads (BPR) model and the Akçelik model outputs. It is found that the proposed method is able to estimate more accurate travel times than traditional methods. The predicted travel time can support freight prioritization and planning.