On-line measurement of engine NOx emissions is the object of a substantial effort, as it would strongly improve the control of CI engines. Many efforts have been directed towards hardware solutions, in particular to physical sensors, which have already reached a certain degree of maturity. In this paper, we are concerned with an alternative approach, a virtual sensor, which is essentially a software code able to estimate the correct value of an unmeasured variable, thus including in some sense an input/output model of the process. Most virtual sensors are either derived by fitting data to a generic structure (like an artificial neural network, ANN) or by physical principles. In both cases, the quality of the sensor tends to be poor outside the measured values. In this paper, we present a new approach: the data are screened for hidden analytical structures, combining structure identification and evolutionary algorithms, and these structures are then used to develop the sensor presented. While the computational time for the sensor design can be significant (e.g. 1 or more hours), the resulting formula is very compact and proves able to predict the behaviour of the system at other operating points. The method has been validated with NOx data from a production engine measured with a Horiba Mexa 7000. The approach is able to yield a good prediction behaviour over a whole cycle. The results are consistent with physical knowledge.