marine (adj.) Look up marine at Dictionary.com
early 15c., "pertaining to the sea," from Middle French marin, from Old French marin "of the sea, maritime," from Latin marinus "of the sea," from mare "sea, the sea, seawater," from PIE *mori- "body of water, lake" (see mere (n.)). The Old English word was sælic.
marine (n.) Look up marine at Dictionary.com
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."