This paper improved the existing navigtion system from the perspective of navigation message design. Through the anglysis of the navigation message design of Beidou Navigation system, the paper proposed a new design of navigation message based on orthogonal frequency division multiplexing (OFDM). The new design enabled a parallel transmission of the ephemeris of all satellites by every satellites, which significantly improved the positioning speed and precision of the medium-long range anti-ship missile. It also used the limited resources of the navigation message more effectively and enhanced the anti-jamming capability of the system, which possessed both advantages and potentials beyond the existing methods. And it had a good significance to improve the flying accuracy of the medium-long range anti-ship missile.