For Inertial Navigation System (INS)/Celestial Navigation System (CNS)/Global Navigation Satellite System (GNSS) integrated navigation system of the missile, the performance of data fusion algorithms based on the Cubature Kalman Filter (CKF) is seriously degraded when there are non-Gaussian noise and process-modeling errors in the system model. Therefore, a novel method is proposed, which is called Optimal Data Fusion algorithm based on the Adaptive Fading maximum Correntropy generalized high-degree CKF (AFCCKF-ODF). First, the Adaptive Fading maximum Correntropy generalized high-degree CKF (AFCCKF) is proposed and used as the local filter for the INS/GNSS and INS/CNS subsystems to improve the robustness of local state estimation. Then, the local state estimation is fused based on the minimum variance principle and high-degree cubature criterion to get the globally optimal state. Finally, the experimental results verify that the proposed algorithm can significantly improve the robustness of the missile-borne INS/CNS/GNSS integrated navigation system to non-Gaussian noise and process modeling error and obtain the global optimal navigation information.