In Mexico, fuel consumption costs are almost a half of the total operational costs in passenger road transportation companies so that even small improvements in this matter can positively affect their profits. This work presents the results of applying a continuous improvement project in the fuel efficiency department for one of the main bus fleets of an important transportation company in the region. We describe the application of the PDCA methodology. During the “Plan” step, we also rely on relevant literature to justify the strategies proposed. Among these strategies are: a new measurement & control system of fuel efficiency, the improvement of the value stream in the maintenance department, a system to increase the fuel energy efficiency through the use of additives, and a new incentive program for drivers. Results on the implemented strategies and estimations for the ones still on progress show that the company will be able to increase up to 3.8% the fuel efficiency of the fleet under study.