In African cities like Nairobi, policies to improve vehicle fuel economy is helping to reduce greenhouse gas emissions and improve air quality, but lack of data is a significant challenge. This paper presents a methodology for estimating fuel economy in such cities. Vehicle characteristics and activity data, for both the formal fleet (private cars, motorcycles, light and heavy trucks) and informal fleet— minibuses (matatus), three-wheelers (tuk-tuks), goods vehicles (AskforTransport) and two-wheelers (bodabodas)—were collected and used to estimate fuel economy. Using two empirical models, general linear modelling (GLM) and artificial neural network (ANN), the relationships between vehicle characteristics for this fleet and fuel economy were analysed for the first time. Fuel economy for bodabodas (4.6 ± 0.4 L/100 km), tuk-tuks (8.7 ± 4.6 L/100 km), passenger cars (22.8 ± 3.0 L/100 km), and matatus (33.1 ± 2.5 L/100 km) was found to be 2–3 times worse than in the countries these vehicles are imported from. The GLM provided a better estimate of the predicted fuel economy based on vehicle characteristics. The analysis of survey data covering a large informal urban fleet helps meet the challenge of a lack of availability of vehicle data for emissions inventories. This may be useful to policymakers as emissions inventories underpin policy development to reduce emissions.