I never knew

Where the phrase "Tell it to the Marines!" came from, but I have located a dandy little anecdote regarding its origin from Colonel John W. Thomason's book "Fix Bayonets."

They relate of Charles the Second that at Whitehall a certain sea-captian, newly returned from the Western Ocean, told the king of flying fish, a thing never heard of in old England. The king and the court were vastly amused. But, the naval fellow persisting, the Merry Monarch beckoned to a lean, dry colonel of the sea regiment, with a seamed mahogany face, and said, in effect: "Colonel, this tarry-breeks here makes sport with us stay-at-homes. He tells us of a miraculous fish that forsakes its element and flies like a bird over the water!" "Sire," said the colonel of Marines, "he tells a true thing. I myself have often seen those fish in your Majesty's seas around Barbados–" "Well," decided Charles, "such evidence cannot be disputed. And hereafter, when we hear a strange thing, we will tell it to the Marines, for the Marines go everywhere and see everything, and if they say it is so, we will believe it!"