I know Latin was a vulgarization in attempting to make Mass more accessible to Christians. So which were the languages used in paleo-Christian Mass? Koine Greek, classical Greek, or something else? What other languages were used, up until the Council of Trent.
In the earliest centuries of the Church, there wasn't a pattern of using liturgical languages, as much as trade languages.
In the East, Greek was predominantly used because whereas it was the first language of few people, it was a second language for many people. It's use could symbolize the internationality of the Church, but more practically, it made it possible for as many people as possible to follow along, if not understand every word. Interestingly enough, Greek predominated in Rome itself, because its heavily international population didn't all speak Latin. By contrast, in North Africa, Latin seems to have been the predominant language almost immediately. Outside of Egypt, Latin was the language of international affairs in North Africa because of its extensive colonization and coordination by Roman authorities. This was also the case in Spain, Britain, and non-Mediterranean France, other regions little influenced by the Greeks. When it was evangelized, Ireland experienced the Mass in Latin. (Nickerson, Jane Soames. A Short History of North Africa. New York: The Devin-Adair Co., 1961, p30.)
In the ninth century, permission was given by the Church to translate the Mass and related texts (such as the scripture) into what is now called Old Church Slavonic. At the time, it was a dated but not quite defunct legal and ceremonial language used in Slavic regions, essentially a mother language to the languages they were speaking at the time. The idea was the same - a single liturgical language for a broad swath of country and for many nations, not exactly native to any of them, but not entirely foreign, either. (Korolevsky, Cyril. Living Languages in Catholic Worship: An Historical Inquiry, trans. Donald Attwater. Westminster, Maryland: The Newman Press, 1957, p3.)
Additionally, Franciscan missionaries to the Mongols were given permission to translate the liturgical rites and the sacred scripture into their language in the 13th or 14th century, provided that the most noble and poetic version of the language be used. In like manner, Jesuits were given permission to translate the same materials into Chinese (Mandarin, I think) in the 16th-17th century, but because of the cultural climate in Europe at the time, they never actually made use of these permissions.
So long answer shortened: Latin was in use in the early Church but, ironically enough, not in the region of Latin's origin. The Church's primary concern was not exactly just that the Mass should be accessible. She was also concerned that the Mass should be transnational.
If you're wondering, while in the seminary, I wrote a paper on topic of liturgical and vernacular language in pre-Christian and Christian worship. My thesis is that the Church has always wanted both accessibility and transcendence in the worship of a God who transcends and makes himself accessible. (Here's a dropbox link. It doesn't seem like a very good way to share the file, but I don't think there's a place to upload or attach PDFs here: Vernacular and Liturgical Language in the Mass