I think in order to answer this question we must first address the misconception of language in the Roman empire. While Latin did prevail as the main language in both speaking and writing within the limited borders of Italy and the surrounding areas, to assume that Latin was the prevailing language (both written and orally) in the vast territory of the Roman Empire at its height would be a mistake. The reasoning for this might become clearer if you think of how quickly the empire expanded and contracted, and how often the Romans were imposing the central Roman culture on peoples already present in the land (here is a good video to illustrate this ) In the case of the Byzantine East the case is quite clear that Latin was rarely a language of the common people, and in fact it was these very cultural and linguistic differences that made the split between the two halves of the empire relatively easy. Here are a collection of contemporaneous sources that illustrate just how stark the difference between the Western and Eastern halves was.

Themistius, a Byzantine politician of the 4th century, declares to the latinophone Emperors that:
"Ουδέποτε, ώ βασιλείς, άναγκαίαν είναι μοι την διάλεκτον την κρατούσαν(την λατινική εννοεί) ύπολαβών, αλλ' ίκανον αεί νομίσας την πάτριον και Έλληνικήν άποχρώντως μεταχειρίζεσθαι." στο λόγο του Φιλάδελφοι ή περί φιλανθρωπίας-Themistios 71c: Ι, σελ. 106,1-4.
"Never, o kings, it was necessary to learn the official language(the latin), but it was enough, I always believe, to know my mother-language Greek."

In 6th century, Ioannes Lydos, in his "Peri archon tes Romaion Politeias", explains that in the eastern provinces of the Empire *: "Hellenas ek tou pleonos ontas"-"Greek are in the most part".*the same writer writes that emperor Phokas "περινοήσαί τινά προς διδασκαλίαν αυτώ της Ίταλίδος φωνής."-"thought to start learn some Latin".

Additional quotes by Acropolites and Chrysoloras, writers in the 14th and 15th century reveal an allegiance to the past as well.
Georgios Acropolites is revealing:
«ὡς ἔοικε γοῦν τῆς ἀρχαίας ἡμετέρας ἀγάπης οὐκέτι ἔχετε μνήμην, ὦ Ἰταλοί. εἰ γοῦν ἐν λήθῃ ταύτης γεγένησθε, ἐγὼ ταύτης ὑμᾶς ἀναμνήσαιμι. οὐκ ἄλλα ἄττα τῶν ἐθνῶν εἰς τοσαύτην προέβη τὴν ὁ μόνοιαν καὶ τὴν σύμπνοιαν ὡς Γραικοί τε καὶ Ἰταλοί. καὶ εἰκότως• ἐκ Γραικῶν γὰρ τοῖς Ἰταλοῖς καὶ αἱ λογικαὶ ἐπι στῆμαι καὶ τὰ μαθήματα. κἀντεῦθεν ἵνα μὴ τοῖς ἐθνικοῖς τούτοις ὀνόμασι περιγράφωνται, τῇ πρεσβυτέρᾳ Ῥώμη ἑτέρα νέα ἀντῳκοδόμηται, ἵνα ἐξ οὕτω μεγίστων πόλεων κοινὸν ἐχουσῶν τοὔνομα Ῥωμαῖοι πάντες κατονομάζοιντο καὶ ὡς τὸ τῆς πίστεως κοινὸν οὕτως ἔχοιεν καὶ τὸ τῆς κλήσεως. καὶ ὡς ἐκ Χριστοῦ ταὐτὸ τὸ τιμιώτατον ἔλαχον ὄνομα, οὕτω καὶ τὸ ἐθνικὸν αὐτοῖς ἐπηγάγοντο. καὶ πάντα δὲ τὰ ἄλλα ὑπῆρχε τούτοις κοινά, ἀρχαὶ νόμοι λόγοι βουλαὶ δικαστήρια, αὐτὴ ἡ εὐσέβεια, οὐδὲν ὅτι μὴ κοινὸν Ῥωμαίοις τοῖς παλαιοτέροις καὶ νεωτέροις.»

“Its seems that our ancient love among us you don’t have remember it, o Italians, and if you indeed forgot that(love), I’ll remind it to you, because with no other nations has such harmony and unity occurred as between Greeks and Italians, because from Greeks Italians got the science and after that the ethnic names weren’t used, and a new Rome was built, and because of these great cities we have common name, and Romaioi all we are called and had the same faith and the same name for it, a name from Christs’ name, so and an ethnic name, and everything we had in common, laws, philology, judgement, and devoutness, and all were shared by old and new Romans”

And the great historian Chalcokondyles, writes:
«… ,ᾤκηται, Βυζάντιον Ἑλληνίδα πόλιν μητρόπολιν σφῶν ἀποδεικνύντας, πρὸς Πέρσας, ὑφ' ὧν ἀνήκεστα ἐπεπόνθεισαν, τὸν ἀγῶνα ποιεῖσθαι, Ἕλληνάς τε τὸ ἀπὸ τοῦδε Ῥωμαίοις αὐτοῦ ἐπιμιγνύντας, γλῶτταν μὲν καὶ ἤθη διὰ τὸ πολλῷ πλέονας Ῥωμαίων Ἕλληνας αὐτοῦ ἐπικρατεῖν διὰ τέλους φυλάξαι, τοὔνομα μέντοι μηκέτι κατὰ τὸ πάτριον καλουμένους ἀλλάξασθαι, καὶ τούς γε βασιλεῖς Βυζαντίου ἐπὶ τὸ σφᾶς αὐτοὺς Ῥωμαίων βασιλεῖς τε καὶ αὐτοκράτορας σεμνύνεσθαι ἀποκαλεῖν, Ἑλλήνων δὲ βασιλεῖς οὐκέτι οὐδαμῇ ἀξιοῦν. …»

“ Byzantion a Greek city was proved a capital, close to Persians, from who many difficulties experienced, and so Greeks with Romans mixed, but language and culture were kept until now the same because Greeks were much more than the Romans, and we’ve changed our fathers’ name, and so the kings of Byzantion were called themselves Kings and Emperors of Romaioi and wouldn’t care to be called kings of Hellenes,…"

I include such a variety of quotes to illustrate just how pronounced this difference was perceived to be. Here is a brief breakdown of the time periods each historian lived in (1st quote: 4th century, 2nd quote: 6th century as well, 3rd and 4th quotes both written in the 14th and 15th centuries). It is clear at least in the eyes of the "common folk" that the Greek identity had been preserved despite the Roman empire, acting as a supranational identity rather than one they identified with personally.

Now comes the question of the official movement from Latin to Greek (legislative and political evidence as opposed to anecdotal descriptions). The emperor to replace Latin with Greek as the majority use language in the official sphere was Heraclius of the 7th century. There is quite a significant debate on this matter, as it is not quite clear when or how this was enacted. Again I would point to the somewhat transitory nature of language (one cannot simply declare everyone speak Greek the next day or Latin or any other language rather), and it is likely that legislation was kept in both languages (for the common people and for the officials as this quote from Neares, where the first collection of laws of the state written officialy in Greek, during Justinian, before Greek became the de facto official language, has it:

"της μεν τη 'Ελλήνων φωνή γεγραμμένης δια το τω πλήθει κατάλληλον*, της δέ τη 'Ρωμαίων, ήπερ εστί και κυριωτάτη,δια το της πολιτείας σχήμα".*
"It is written in Greek because it is suitable for the masses, and in Latin, for the tradition of the state"Nov.LXVIl,2.

What is clear however is that in the following centuries the Byzantines distanced themselves ever further from whatever Latin connection they might have felt. While they might have considered themselves Roman, their cultural ties to the West grew ever strained. This could be demonstrated in the Schism in Christianity. The Byzantine Greeks might have considered themselves true inheritors of the empire of Rome, but the West likely did not, and rather used this "otherness" to justify actions such as the election of Charlemagne as the Holy Roman Emperor and the Crusades in the following centuries. The matter of self identification is also questioned but it truly did not occur until the 12th century, the Byzantines identifying more with the idea of a Greek speaking Roman people, but that is another tricky and tangential subject for another time.

TL;DR- Greek was the language of the common people for a long time, and while the evidence is scanty as to when the official language changed it began to change around the 7th century as further cultural divergence occurred.