Methods and systems for enhancing the detectability of maritime e-Navigation messages are provided. Transmitters apply error protection encoding to the payload portion of messages to be transmitted, which are wrapped in a standard e-Navigation message format such as that used by the Automatic Identification System. Transmitted messages are received by a satellite or other surveillance platform employing a compatible radio frequency receiver to collect message signals over a large area or great distance. Candidate messages are identified and the error protection encoding decoded to recover messages.