A two-dimensional optimization process, which simultaneously adjusts the spark timing and equivalence ratio of a lean-burn, natural gas, Hercules G1600 engine, has been demonstrated. First, the three-dimensional surface of thermal efficiency was mapped versus spark timing and equivalence ratio at a single speed and load combination. Then the ability of the control system to find and hold the combination of timing and equivalence ratio that gives the highest thermal efficiency was explored. NOx, CO, and HC maps were also constructed from our experimental data to determine the tradeoffs between efficiency and emissions. The optimization process adds small synchronous disturbances to the spark timing and air flow while the fuel injected per cycle is held constant for four cycles. The engine speed response to these disturbances is used to determine the corrections for spark timing and equivalence ratio. The control process, in effect, uses the engine itself as the primary sensor. The control system can adapt to changes in fuel composition, operating conditions, engine wear, or other factors that may not be easily measured. Although this strategy was previously demonstrated in a Volkswagen 1.7 liter light duty engine (Franklin et al., 1994b), until now it has not been demonstrated in a heavy-duty engine. This paper covers the application of the approach to a Hercules G1600 engine.