In modern automotive engines, air-fuel ratio (AFR) strongly affects exhaust emissions, power, and brake-specific consumption. AFR control is therefore essential to engine performance. Most existing engine built-in AFR controllers, however, are lacking adaptive capability and cannot guarantee long-term control performance. Other popular AFR control approaches, like adaptive PID control or sliding mode control, are sensitive to noise or needs prior expert knowledge (such as the engine model of AFR). To address these issues, an initial-training-free online sequential extreme learning machine (ITF-OSELM) is proposed for the design of AFR controller, and hence a new adaptive AFR controller is developed. The core idea is to use ITF-OSELM for identifying the AFR dynamics in an online sequential manner based on the real-time engine data, and then use the ITF-OSELM model to calculate the necessary control signal, so that the AFR can be regulated. The contribution of the proposed approach is the integration of the initial-training-free online system identification algorithm in the controller design. Moreover, to guarantee the stability of the closed-loop control system, a stability analysis is also conducted. To verify the feasibility and evaluate the performance of the proposed AFR control approach, simulations on virtual engine and experiments on real engine have been carried out. Both results show that the proposed approach is effective for AFR regulation.