This contribution reports the results of comprehensive quantum-mechanical calculations of low-temperature oxidation (i.e., below the softening point) of polyethylene (PE) film in a corrosive NOx environment, by mapping out the potential energy surface for a large set of reactions, developing thermokinetic parameters for each elementary reaction and discussing in detail the most energetically favorable paths. Remarkably, addition of nitric oxide (NO) and nitrogen dioxide (NO2) results in formation of C-nitroso and nitro species, respectively, and successively leads to internal tautomerisation or concerted elimination of nitroxyl (HNO) and nitrous acid (HNO2). We demonstrate that, the presence of molecular oxygen sustains the formation of O-nitroso compounds, organic nitrites and nitrates. Reaction rate parameters have been established for all considered reactions over the temperature range of 300 to 800 K. The results presented herein provide new insights into the solid-state polymer-gas reactivity of PE in NOx atmosphere pertinent to thermal recycling of materials laden with PE and to cocombustion of PE with a nitrogen-rich fuel such as biomass. The results will find application to systems that involve oxidative decomposition of germane crystalline polyolefins/paraffins and pure carbon-hydrogen-type polymers induced by aggressive gases such as NO and NO2.