Other Fish in the Sea

Does anyone know where the following phrase comes from?

"There are other fish in the sea."

Thanks,
Bev

There are other fish in the sea. There are even better ones out there. Don't be upset over what you've lost. This proverb is often used as a consolation for losing a girlfriend or a boyfriend, and has been traced back to about 1573. First attested in the United States in _Keziah_ by J. C. Lincoln, the proverb is found in varying forms: "There are plenty more fish in the sea"; "There are more fish in the sea than ever came out of it"; "The sea is full of other fish"; "There's more than one fish," etc.
From _Random House Dictionary of Popular Proverbs & Sayings_ by Gregory Titelman
----------
In the mayne sea theres good stoare of fishe, And in delicate gardens ... Theres alwayes greate varietye of desirable flowers. (c1573; G. Harvey, _Letter-Book_, 1884)
There never was a fish taken out of the sea, but left anothe as good behind. (T.L. Peacock, _Headlong Hall_, 1816)
Ye need not sigh sae deeply.... There are as gude fish in the sea as ever came out of it. (Scot, _Nigel_, 1822)
There's fish in the sea, no doubt of it, As good as ever came out of it. (Gilbert, _Patience_, 1881)