The relationship between the ancient Greeks and the medieval Byzantines was... complicated, to say the least. For one, of course, we do have to recognize that the medieval empire was a multiethnic state, and many of its citizens had no vested interest in any continuity with ancient Greece. Even among Greek-speaking rhomaioi, however, the existence and precise nature of the state and people's connection to the ancient past was a matter of debate: while many intellectuals were happy to claim that the adoption of Christianity marked a total boundary between the two periods, others proudly claimed the ancient Greeks as their forebears and their traditions as historically viable (albeit rewritten to accommodate the new Christian worldview). I've discussed some of the broader aspects of this relationship in some answers to prior questions: Was the Byzantine Empire Roman or Greek?, Did Greek-Speaking citizens of the "Byzantine" Empire consider themselves primarily as Greek or Roman?.

So let's talk about Byzas and the foundation of Byzantium! The short answer to your question is yes, there are definitely medieval accounts of the city's history in which a king named Byzas plays a central role, but they aren't the only version of the story. I'll briefly (very briefly) talk about some of the other versions at the end of this post, but for now, the focus is on Byzas. (Specifically, Byzas in Eastern Roman sources after the fifth century; there's a lot to be said about earlier traditions as well, but I'm not the man to say it.)

One of the earlier Byzantine histories to mention Byzas is the Patria of Constantinople by Hesychius of Miletus, who lived and wrote during the reign of Justinian (mid-6c.). Now, Hesychius is a bit of a complicated character for our purposes here, not least because it's not entirely clear whether he was Christian or pagan (Kaldellis's article, cited below, makes good arguments for both sides). If the latter, of course, we might not be too surprised to see him writing a history of Constantinople based on pagan myth. But the fact remains that even if Hesychius was himself pagan, he was writing in a Christian context, and so the reference to Byzas is significant: in fact, three references, the most plausible of which (to Hesychius) was that Byzas was a grandson of Io who, like Laomedon of Troy, contracted with Apollo and Poseidon to build the walls of the nascent Byzantium.

A much more abbreviated (and more amenable to Christian ears) version of the story appears in the Chronicle of Hesychius's contemporary, the Syrian historian John Malalas. (We can also find references around this time by Procopius, Stephen of Byzantium... the list goes on!) Malalas's account is so abbreviated, in fact, that it's possible to quote in full here:

This city had originally been built by Phidalia ... Phidalia had been married to Byzas, the king of Thrace, after the death of her father Barbysios, who was the toparch and warden of the port. Barbysios on the point of death told Phidalia to make a wall for the place down to the sea. Byzas named the area after himself and ruled in the city.

Io, Apollo, and Poseidon are notably absent from this version, and in the quoted passage it's even a little unclear whether Byzas did anything to justify naming Byzantium after himself: most of the work seems to have been done by Phidalia, and perhaps in a less patriarchal age the city would have been Phidaliapolis instead.

In another version, he would be joined by a second founder named Antes. Byzas-Antes—ByzAntium—a back-and-forth between etymology and etiology, as was so common in medieval historiography. Here we turn to a chronicle written a few centuries after Hesychius's Patria, the eighth-century Parastaseis syntomoi chronikai. This version of the story is notable among other things for its confused chronology, an attempt to neatly write Byzas and Antes into Christian history: the kings are not explicitly named as founder of the city, but as opponents of Constantine. Note: I've seen a few authors cite this as evidence for a wider historiographic tradition, but I've also never seen another example, so take with a grain of salt. But, as we saw with Hesychius, even if we treat the Parastaseis and the addition of Antes as exceptional, the mere fact of its existence is evidence for the continuing relevance of the Byzas myth in Christian Constantinople.

In the eleventh century, we see the "Thracian king" Byzas mentioned by George Cedrenus; as late as 1429, the future metropolitan/apostate/cardinal Isidore of Kiev mentions his legend in an encomium to John VIII. The phrase "city of Byzas" (which does not of course presuppose any faith in Byzas's historicity) runs as a thread through Malalas (6c.) and Michael Attaleiates (11c.) to the poetry of Manuel Korinthios (late 15c.) and the prophetic and revolutionary Vision of kyr Daniel (18c.). It is safe to say that the Byzas legend was enduring enough for these references to remain legible for centuries: indeed, if we consider the latter two examples, it seems Byzas outlasted the Byzantines!

Of course, as I stressed at the beginning, Byzas's claim to have founded the city did not go uncontested. But many of his competitors represented ties to a Hellenic past: the tenth-century emperor Constantine Porphyrogenitus, for example, referred to Byzantium as the product of colonists from Megara, Boeotia, and Sparta. It would have been difficult to do otherwise. Even if Greek mythology had fallen out of favor, Greek historians had not, and authors like Herodotus and Diodorus Siculus (both of whom remained on the radar of educated Byzantines, and the latter of whom explicitly mentions Byzas) explicitly mentioned the city's Hellenic roots. There were still a few ways to downplay any Greek contribution to medieval Constantinople: one could ignore the distant past in favor of the post-Constantinian period, for example, or argue that while the Greeks came first, the Romans contributed more to the overall character of the city. But when push came to shove, the fact that Byzantium was at one point a Greek colony could never be denied.

Some reading on the subject:

Anthony Kaldellis, "The Works and Days ofHesychios the Illoustrios of Miletos," Greek, Roman, and Byzantine Studies 45 (2005): 381-403. [PDF]

Averil Cameron and Judith Herrin, eds. and trans., Constantinople in the Early Eighth Century: The Parastaseis Syntomoi Chronikai (Leiden: Brill, 1984).

Aslıhan Akışık-Karakullukçu, "From 'Bounteous Flux of Matter' to Hellenic City: Late Byzantine Representations of Constantinople and the Western Audience," in Representations of Hellenism in Early Modern Europe, ed. Natasha Constantinidou and Han Lamers (Leiden: Brill, 2019), 145-172. [academia.edu]

John Malalas, The Chronicle of John Malalas, ed. and trans. Elizabeth Jeffrys, Michael Jeffrys, and Roger Scott (Melbourne: Australian Association for Byzantine Studies, 1986).

Thomas Russell, Byzantium and the Bosporus: A Historical Study, from the Seventh Century BC until the Foundation of Constantinople (Oxford University Press, 2017).