Road freight transport is of critical importance for economic growth in Sub-Sahara Africa due to lacking rail infrastructure. Fuel represents the single biggest operational cost for road transport operators; improved fuel efficiency is therefore a priority to achieve global competitiveness in corridors that link the hinterland with the global economy. This paper quantifies the factors that impact fuel utilization with the aim of correctly estimating fuel consumption for new routes. These factors include driver behavior, engine size, vehicle fabrication, payload, traffic conditions and route inclinations. Fuel usage data was collected for a fleet of more than 400 trucks covering major routes in Southern Africa over a complete calendar year. This data was categorized based on driver identity, route and vehicle model. We determined the impact of each input factor on consumption in order to select suitable inputs to allow the development of a route fuel consumption model. A linear regression model was then extracted from a training set to predict consumption based on the selected inputs. The model was applied to a set of unseen test data, and found to possess significant out-of-sample predictive ability, allowing the fuel cost for new routes to be estimated before actual fuel consumption data has been generated.