NOx formation from a methane - air diffusion flame in a two-dimensional jet involving highly preheated air, which has recently become an important topic in industrial furnaces, is investigated numerically using a full chemistry approach including C2, prompt and thermal mechanisms. Effects of increased air temperature on NOx formation are examined. Numerical results show that both NO formation mechanisms increase dramatically with increasing air temperature. A C-shaped production zone of NOx, corresponding to the fuel-lean and fuel-rich regions of triple flame, is identified. It is shown that NO formation with high air temperature can be suppressed efficiently by decreasing the oxygen concentration in the airstream. Production rate analyses of elementary reactions are made. Formation paths of NOx at low and high temperatures are obtained and compared. The results show that the NOx formation path depends strongly on the air temperature. In addition to the thermal route and the HCNNO route, the HCNCN and NOCN recycling routes are greatly enhanced at high air temperature. The results show that the prompt mechanism and the thermal mechanism are strongly coupled at high air temperature. Calculations of prompt NO and thermal NO in a two-dimensional jet and in the counterflow configuration reveal that the conventional method cannot give a correct prediction of prompt NO and thermal NO, particularly at high air temperature. A method using the concept of fixed nitrogen is presented. Numerical results indicate that the formation process of prompt NO and thermal NO can be evaluated properly by the present method.