Recent research has proven that computational fluid dynamics (CFD) modeling in combination with a genetic algorithm (GA) algorithm is an effective methodology to optimize the design of internal combustion (IC) engines. However, this approach is time consuming, which limits the practical application of it. This study addresses this issue by using a quasi-dimensional (QD) model in combination with a GA to find optimal fuel composition in a spark ignition (SI) engine operated with CH4/H2/CO fuel blends. The QD model for the simulation of combustion of the fuel blends coupled with a chemical kinetics tool for ignition chemistry was validated with respect to measured pressure traces and NOx emissions of a small size single-cylinder SI engine operated with CH4/H2 blends. Calibration was carried out to assess the predictive capability of the QD model, and the effect of hydrogen addition on the lean limit extension of the methane fueled engine was studied. A GA approach was then used to optimize the blend composition and engine input parameters based on a fitness function. The QD-GA methodology was implemented to simultaneously investigate the effects of three input parameters, i.e., fuel composition, air–fuel equivalence ratio and spark timing on NOxemissions and indicated thermal efficiency (ITE) for the engine. The results found indicated that this approach could provide optimal fuel blends and operating conditions with considerable lower NOx emissions together with improved thermal efficiencies compared to the methane fueled engine. The presented computationally-efficient methodology can also be used for other fuel blends and engine configurations.