Exergy or availability is the potential of a system to do work. In this paper, an innovative exergy-based control approach is presented for Internal Combustion Engines (ICEs). An exergy model is developed for a Homogeneous Charge Compression Ignition (HCCI) engine. The exergy model is based on quantification of the Second Law of Thermodynamic (SLT) and irreversibilities which are not identified in commonly used First Law of Thermodynamics (FLT) analysis. An experimental data set for 175 different ICE operating conditions is used to construct the SLT efficiency maps. Depending on the application, two different SLT efficiency maps are generated including the applications in which work is the desired output, and the applications where Combined Power and Exhaust Exergy (CPEX) is the desired output. The sources of irreversibility and exergy loss are identified for a single cylinder Ricardo HCCI engine. Based on the SLT efficiency contour maps, an optimization algorithm is designed to determine the optimum combustion phasing at every given engine load to maximize the SLT efficiency. Application of the optimization algorithm is illustrated for tracking of combustion phasing. The results show that using the exergy-based optimal control strategy leads to an average of 5.4% fuel saving for both applications, compared to commonly used FLT based combustion control in which a fixed combustion phasing (i.e., 8 CADaTDC) is used. While a number of studies have been conducted on exergy analysis of ICEs, to the best of the authors’ knowledge, this paper is the first study undertaken to construct an exergy-based control strategy for ICEs.