I'm sure you're aware that Basileus is Greek for 'king'. I guess the question is, how did a Greek title come to be used for the leader of what used to be the Roman Empire?

You need to understand a couple of things here:

Even though the Eastern Mediterranean had been incorporated into the Roman Empire from the third century BC, it retained its existing language and much of its culture throughout the Roman period. Thanks to the conquests of Alexander in the fourth century BC, this culture was predominantly Greek. Alexander was himself a Greek and spread his Greekness wherever he went, which was throughout what we would call the Near East.

In 284 AD, the Emperor Diocletian split the Empire into two halves, creating the Western Roman Empire, centred on Rome, and the Eastern Roman Empire, centred on Byzantium (later Constantinople, and later still Istanbul). The Western half was more or less Latin-speaking, while the Eastern half was more or less Greek-speaking.

This Greek-speaking Empire survived the fragmentation and fall of the Western Empire by almost a thousand years, giving rise to all kinds of Greek titles which are still used today - especially in relation to the church.