A counter-flow air-fuel heat exchanger can be applied in an advanced aero engine to effectively decrease the high-pressure air temperature and thus recover its cooling capacity. However, the fuel, kerosene, is susceptible to thermal oxidative reactions in the heat exchange process, causing surface coking that would degrade the long-term heat exchange performance. Numerical studies have been conducted to investigate the long-term (15 h) heat exchange process between the supercritical-pressure (3 MPa) kerosene and high-pressure air (4 MPa) in a counter-flow heat exchanger, employing a detailed 35-step chemical reaction mechanism and a dynamic mesh moving method. The transient coking layer thickening process from thermal oxidative reactions was simulated, the coupled characteristics of thermal oxidative coking and heat exchange were analyzed under different air mass flow rates and initial dissolved oxygen mass fractions, and the effects of surface coking on the total heat transfer coefficient, Number of Transfer Units (NTU), and effectiveness (ε_eff) in the counter-flow heat exchanger were quantitatively evaluated. Results indicate that at an increased air mass flow rate, thus with the enhanced heat exchange rate, locations of the maximum surface coking rate and the entire coking layer inside the fuel tube move upstream, but the peak coking layer thickness remains essentially unchanged. The coking layer thickness in the middle and downstream regions can be significantly reduced as the initial dissolved oxygen mass fraction is decreased, improving heat exchange process in the corresponding regions. Gradual accumulation of the surface coking layer leads to heat exchanger performance deterioration, and a linear relationship is found to exist between the nondimensionalized NTU and nondimensionalized ε_eff in the studied cases.