This work presents a new method for online fuel-efficiency optimization of Diesel engines, using constrained extremum-seeking. A two-input optimization problem, which is suitable for extremum-seeking, is integrated into a tracking control system. As a result, both air-path and fuel-path actuators are used for tracking and extremum-seeking. A key element of the proposed method is a cost function based on real-time BSFC estimation. Moreover, an existing constrained extremum-seeking method is extended to multiple output constraints. Experiments on a Euro-VI heavy-duty Diesel engine demonstrate the constraint handling, robustness with respect to real-world disturbances, and the fuel saving potential of the control design.