14c., "seacoast;" see marine (adj.). Meaning "collective shipping of a country" is from 1660s. Meaning "soldier who serves on a ship" is from 1670s, a separate borrowing from French marine, from the French adjective. Phrase tell that to the marines (1806) originally was the first half of a retort expressing skepticism:
"Upon my soul, sir," answered the lieutenant, "when I thought she scorned my passion, I wept like a child."
"Belay there!" cried the captain; "you may tell that to the marines, but I'll be d----d if the sailors will believe it." ["John Moore," "The Post-Captain; or, the Wooden Walls Well Manned," 1805]
The book, a rollicking sea romance/adventure novel, was popular in its day and the remark is a recurring punch line in it (repeated at least four times). It was written by naval veteran John Davis (1774-1854) but published under the name John Moore. Walsh records that, "The marines are among the 'jolly' jack-tars a proverbially gullible lot, capable of swallowing any yarn, in size varying from a yawl-boat to a full-rigged frigate."