Thessalonike was the daughter of Phillip II of Macedon, and a half sister to Alexander III of Macedon. Legend has it that when Alexander died, Thessalonike "became a mermaid passing judgment on mariners":
There exists a popular Greek legend which talks about a mermaid who lived in the Aegean for hundreds of years who was thought to be Thessalonike. The legend states that Alexander, in his quest for the Fountain of Immortality, retrieved with great exertion a flask of immortal water with which he bathed his sister's hair. When Alexander died his grief-stricken sister attempted to end her life by jumping into the sea. Instead of drowning, however, she became a mermaid passing judgment on mariners throughout the centuries and across the seven seas. To the sailors who encountered her she would always pose the same question: "Is Alexander the king alive?" (Greek: Ζει ο βασιλιάς Αλέξανδρος;), to which the correct answer would be "He lives and reigns and conquers the world" (Greek: Ζει και βασιλεύει, και τον κόσμο κυριεύει!). Given this answer she would allow the ship and her crew to sail safely away in calm seas. Any other answer would transform her into the raging Gorgon, bent on sending the ship and every sailor on board to the bottom.
Wikipedia contributors, 'Thessalonike of Macedon', Wikipedia, The Free Encyclopedia, 16 June 2015, 18:36 UTC, https://en.wikipedia.org/w/index.php?title=Thessalonike_of_Macedon&oldid=667233592 [accessed 22 June 2015]
Almost every version I've read mentions Alexander's search for the fountain of youth, which points to the legend being part of the Alexander romance. However, I haven't been able to pinpoint a possible source for the legend or even get a vague idea of when it first appeared.