Most of the times I read about the Eastern Roman Empire, I find a reference along the lines of "at this point, they had abandoned Latin and only spoke Greek". I've never found out when did this happen (and why), and whether this was a gradual process or the product of some emperor's decree.
I know that back in the early first century, Greek was the "educated language" in pretty much all of the Near East, but Latin was the one in official documents because Roman Empire. But that was quite before the Roman Empire's partition... did Latin never really gain its foothold as the primary language in the region, to begin with?
The eighth century Greek historian, Theophanes, sixth century Greek historian, Procopius, records that in 535, Emperor Justinian (527-565) decreed that Greek should be the 'language of the state'. This was despite Justinian himself being a Latin-speaking Illyrian, and many of his generals and diplomats speaking Latin as their first language too. By the sixth century, the common language in Constantinople's streets, churches and culture was increasingly Greek, and the senate, courts and army were following suit. Justinian saw this transformation in motion and because of it, decided to make the state's language uniformly Greek.
Edit - Got my sources mixed up.
The honest answer would be that it was a gradual process. Others have already brought up Justinian and Heraclius as two emperors who may have initiated this change, but our evidence is slim and certainly can't be extended to every area of administration - the empire still ruled Latin-speaking territories, so it is less than logical for local administrators to switch to Greek. Why is the evidence problematic? Justinian did issue new laws in Greek, but only for Greek-speaking territories, for Latin-speaking territories it was either in Latin or issued in both languages. Use of Greek in legal texts is also not evidence for language use in the rest of the administration. John Malalas, a contemporary Greek chronicler but also a retired bureaucrat from Antioch seemingly had little to no knowledge of Latin, so I'd suggest that Latin wasn't used very much in the Prefecture of the East for a while already. At the same time, John Lydus, a bureaucrat working under the praetorian prefect in Constantinople, complained bitterly that less and less officials were learning Latin - for him, knowledge of Latin was an essential part of being Roman. John Lydus also cited the example of a praetorian prefect from the time of Theodosius II (408-450) who issued his decrees in Greek, which complicates the picture further. From my perspective the empire was still vast and the regional differences many, so I don't think we can pinpoint exactly when Greek became 'officially' favoured.
Anyway, even if Justinian did replace Latin with Greek, the Latin language continued to flourish. It was the language of a minority, but it was the language of a powerful minority. Justinian and his fellow Illyrians spoke Latin, old families from Italy and North Africa now resident in Constantinople spoke Latin, the Greek elite spoke Latin. Two telling examples would be Corippus, a North African poet, and Pope Gregory the Great. Both men served in Constantinople and both prospered immensely; Corippus delivered a lengthy Latin panegyric for Justin II (565-578) and was presumably rewarded handsomely, whilst Gregory in his capacity as the papal ambassador did just fine even though he admitted that his Greek was terrible. Parts of the administration may well have adopted Greek or may even have always used Greek, but Latin culture in the capital declined slowly. Likewise, not much would have changed in Latin-speaking territories like Italy, though Latin-speakers in the Balkans must have been under pressure from the increasing number of Slavs migrating into Roman territories. Many individuals in the Church continued to be bilingual as well, something that is most visible in the struggle against the condemnation of the Three Chapters under Justinian and monothelitism under Constans II. In both cases ecclesiastics from across the Mediterranean joined the doctrinal debate and formed alliances with theologians in other regions. Bilingualism seems to me to be a fundamental part of the Mediterranean world at this point, so for the elite this did not change, at least for the period I've studied.
As for Heraclius, our evidence comes from his titulature, as he seeming abandoned the old title of augustus and used the Greek basileus instead in the 620s. Personally, I don't think it mean all that much given how flexible titles were in late antiquity. From off the top of my head I know that Roman emperors can be described as reges/kings and that barbarians can easily embrace the titles of imperator and augustus. We know that Heraclius changed his title, but that's it, so we really can't confidently place the complete change of language at this point either. His gold coins, and indeed his successors, for example continued to use Latin (Victoria, Augustus etc). An interesting thing that I noticed just now is that the silver/bronze coins of Constans II (641-668) had the Greek "en toutoi nika" on them, even the ones minted in Carthage, which to me suggests that different parts of the government aimed at different sections of society used different languages. Whereas the elite might have expected Latin on their coins, the common people might have been committed to coins with the traditional Greek on them. This is just personal speculation of course as I'm not a numismatist, but I have to emphasise again how the other answers here are speculations too, as they are extrapolating wider trends from ultimately just two pieces of evidence. More generally speaking, our knowledge of the seventh century is exceptionally poor, so a seemingly confident statement like X happened in Year Y is an especially bad choice when discussing this period of history.
tl; dr - It was a gradual process and we know very little about it.
did Latin never really gain its foothold as the primary language in the region, to begin with?
No. The primary spoken language was Latin only in the western provinces of the Empire, but from the central Balkans it transitioned to Greek.
The official language of the Empire was changed to Greek during the reign of Heraclius 610-641 AD.
The turning point in the changing of the language (at least officially, since greek was spoken by the majority of not educated people) was the reign of Heraclius the young. In 626 Heraclius passed a law that established the use of the term "Basileus" as the official title of the head of state of the Byzantine Empire. This move increased the use of greek as an official language by the elite, who began to translate the legal texts (including the Corpus Iuris Civilis of Justinian). The use of the title "Basileus", however, was not introduced by Heraclius, but discontinuously by previous emperors, like emperor Maurice who was called "Basileus Romaion" (Sovereign of the Romans) instead of "Kaisar Romaion", the Hellenized version of the Latin title, when he wrote to the Sassanid Emperor, Chosroes II. Greek was still spoken since the days of the early Roman emperors as a second language and "language of culture" by nobles and wealthy merchants, since it was the lingua franca of the Eastern Mediterranean by the conquest of Alexander and the consequent Hellenization and the sons of the nobility traveling in Greece to learn oratory by Greek masters
Bibliography:
History of the Byzantine State, Georgije Ostrogorski
The Title Βασιλευσ in Early Byzantine International Relations, Evangelos K. Chrysos