Romania is a relatively young country, having been created only in 1860s, largely from the Wallachia and Transylvania. And indeed, like most countries with Orthodox Christianity being a dominant religion, lands that now form the territory of Romania adopted the Eastern alphabet based on Greek. The first documents written in languages associated with Romanian, then called Wallachian or Moldavian, were written in the local variant of Cyryllic script. It should be noted however, that the region that is now Romania always was (and in many ways, still is) a cultural melting pot, with the strong presence of Germans dating back to the 12th centuries (I touched on the subject in this thread), as well as that of Hungarians and also Poles, so Latin alphabet also had a presence there. Latin script and language was used at least to some extent in the region as evidenced by e.g. coins minted by Moldavian prince Alexandru cel Bun in early 15th century or the description of agreement made in 1480s between prince Stefan III of Moldavia and Polish king Kazimierz IV.
Late medieval and early modern documents written in Transylvania and Wallachia, as in many other region with predominant Eastern Orthodox faith were largely written in Church Slavonic, an Greek counterpart to Latin, commonly used for the same purpose in Western and Central Europe. Local dialects slowly emerged somewhere in late medieval period, around 15th and early 16th century, as evidenced by e.g. Neacșu Letter, written by Wallachian aristocrat in language that merges local Walachian with Church Slavonic, with both being written with Eastern script. The linguistic shift occured largely in 16th and early 17th century, as in the second part of the latter, official documents were largely written in early form of Romanian. In addition, although the first translation of a Bible to Romanian has been printed in 1688 in Bucharest, Church Slavonic retained its position as the language of religion.
Union between the Transylvanian Eastern Orthodox Church and Roman Catholic Church signed in 1700 in Alba Iulia contributed to the rebirth of the Romanian language that was later boosted by the rise of nationalist tendencies and formation or national identity in late 18th and early 19th century. Another angle of the switch towards the Western Europe was the political realization that the alliance with Russian Empire, initially sought in an attempt to counter the Ottoman influence, might eventually result in Russian dominance, especially after Russia annexed Besarabia in 1812.
The second half of the 18th century brings the birth of the 'Transylvanian school' (rom. Școala Ardeleană) uniting many scholars, predominantly members of Greek Catholic clergy, who supported popularization of Romanian, introducing it into the liturgy, promoting Romanian literature and eventually also pushing for the usage of Latin alphabet to transcribe it. Their successors, The Latinist Movement largely focused on stressing the Latin origin of Romanian, what led to some radical ideas that were commonly criticized, such as the transcription reflecting the original Latin roots rather than actual Romanian pronunciation. Meanwhile, in Wallachia and Moldavia, similar attempts took place, as the push for the Western script proposed by Titu Maiorescu, although these were more focused on introduction of words and lexemes from Romance languages, primarily from French. These changes gained more acceptance throughout the first half of 19th century, what led to a problem that underlies the topic at hand. With the substantially higher percentage of the Romance-based words, Romanian language became less suited to be written in Cyryllic, primarily designed to reflect sounds typical for Slavic languages. This does not mean that Romanian had especially strong Slavic elements in previous centuries, as writing was largely limited to official documents. For example, the first known text written in Polish is a single sentence in an otherwise Latin book written around 1270, three centuries after the Christianization of Poland. 'Re-Romanization' of Romanian made it more suitable to be written with Latin script.
As a side note, an opposite attempt was made in Russian Partition of former Poland. After the failed Uprising of 1863, Russian authorities, led by State Secretary Nikolai Milutin, published educational books for rural schools that were written in Polish but transcribed in Cyryllic, to sever the ties with largely Western Polish culture. This short-lived experiment was abandoned after the policy of complete Russification has been introduced few years later. This illustrates that the selection of script used in the area could have and had been influenced by politics.
Romanian language continued to be written in Cyrillic until second quarter of 19th century, when the hybrid Latin-Cyryllic script has been introduced and popularized by Ion Heliade Radulescu's 'Grammar'. In 1862, the decree issued by Alexandru Ioan Cuza replaced it with a Latin script as an official way of transcribing Romanian in United Duchies of Romania, as a part of reforms that were to bring United Duchies closer to the Western Europe and included e.g. adoption of Legal Code based on Napoleonic one, abolition of the nobility privileges and extension of voting rights. Romanian Orthodox church continued to use Cyryllic script in liturgical text until Synod of 1881, when the Latin alphabet has also been adopted into religious literature.
So to sum it up, Romanians (or rather, Wallachians, Transylvanians and Moldavians) who could write were using Cyryllic script before the second half of the 19th century, sometimes using also Latin alphabet for some purposes. It has been switched to Latin script in the wake of religious politics that brought the Orthodox Church closer to Rome and the budding national tendencies in Romania that resulted in the pro-Western tendencies.
Boia, L., Romania: Borderland of Europe. Reaktion Books, London 2001.
King, C., The Black Sea: A History, Oxford University Press, 2005.