A piece on sharks and the like in the National Post mentions:

But this is nothing new. Every seaside civilization in human history has somehow incorporated the shark into its culture. Archaeologists in Italy have found depictions on pottery of attacks by giant fish as far back as 725 BC. Likewise, the ancient Greek historian Herodotus famously depicted a "marine monster" attacking sailors in 492 BC.

Not sure about the pottery depictions, but the passage from Herodotus apparently relates to the destruction of the Persian fleet near Mt. Athos (and seems to be a misreading):

This was the stated end of their expedition, but they intended to subdue as many of the Greek cities as they could. Their fleet subdued the Thasians, who did not so much as lift up their hands against it; their land army added the Macedonians to the slaves that they had already, for all the nations nearer to them than Macedonia had been made subject to the Persians before this. [2] Crossing over from Thasos they travelled near the land as far as Acanthus, and putting out from there they tried to round Athos. But a great and irresistible north wind fell upon them as they sailed past and dealt very roughly with them, driving many of their ships upon Athos. [3] It is said that about three hundred ships were lost, and more than twenty thousand men. Since the coasts of Athos abound in wild beasts, some men were carried off by beasts and so perished; others were dashed against the rocks; those who could not swim perished because of that, and still others by the cold.

(via the Perseus Project ... here's the Greek)