mid-15c., "found in or pertaining to the sea," from Old French marin "of the sea, maritime," and directly from Latin marinus "of the sea," from mare "sea, the sea, seawater," from PIE root *mori- "body of water." The Old English word was sælic.
late 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 (1805) originally was the first half of a retort expressing disbelief in some statement made or story told:
"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 pseudonym "John Moore." Walsh records that, among sailors, marines are "a proverbially gullible lot, capable of swallowing any yarn, in size varying from a yawl-boat to a full-rigged frigate."