Towards the complex channel environment and the inter-carriers interference (ICI) caused by Doppler frequency offset, a time domain adaptive algorithm based on normalized least mean square (TD-NLMS) is proposed to eliminate the interference caused by the carrier frequency offset (CFO) in aeronautical mobile communication OFDM system. In this algorithm, the CFO in time domain is estimated and compensated, and then the residual CFO is eliminated with TD-NLMS method. The simulation results show that in the aeronautical mobile channel environment, the use of the proposed algorithm can not only compensate the phase rotation, but also reduce the bit error rate to improve the accuracy and eliminate the CFO compared with that of the least square (LS) algorithm.