First of all a simple clarification of terminology (with some more details farther below), but that needs to be put forward:

• Why "Moldavia" and "Moldova"? Are they two different things? No. "Moldova" is the name of the region in the Romanian language, which is spoken in Romania and the Republic of Moldova. "Moldavia" in English comes from the French name of the region (Moldavie); "Moldova" has become used in English since the independence of ex-Soviet Republic of Moldova (the name of which might very well have been "Republic of Moldavia" in English, like in French).

• Republic of Moldova and Moldavia/Moldova: are they two different things? In a way yes: to put it shortly, the first is a part of the second. Moldavia/Moldova was a principality that existed between 1359 and 1859. In 1812 Russia took a part of it, namely the region East of the Prut river, and created the governorate of Besserabia. That name was initially referring only to the south of the conquered region (see maps farther below), called thus because until 1367 it was a possession of the Wallachian princes of the Basarab dynasty. (To make things even more blurry: that southern region was taken by the Turks from Moldavia in the 16th century, renamed Budjak, and is now in Ukraine. - See maps below.) Meanwhile, the principality of Moldova/Moldavia (with the capital and most cities situated West of Prut river) continued to exist until its unification with Wallachia in 1859 under a new state called Romania, which in 1918 was able to take back from Russia the rest of Moldavia (the part that had become known as Besserabia). The URSS recuperated Besserabia between 1940-41 and 1944-1991, where it created the Soviet Republic of Moldova (largely on the same territory, with some exceptions: the south went to Ukraine, some territory east of Dniester was added).

• Wallachian and Romanian - is there a difference? Yes and no. Wallachian may mean "from Wallachia" in English (while not all Romanians are from Wallachia), but with that meaning it is used in Romanian only in academic/historical context; otherwise it is rarely used and, if it is, the term "Valah" doesn't mean "people from Wallachia", but "Romanian": it's Wallachia that means "country of the Wallach/Vlach/Valah". Similarly, "Romania" appeared only in the 19th century to name the country (whose people only then started to be called "Romanians" in foreign languages), but in the Romanian language it is the name of the people ("Român") and of the language ("româneşte", "limba românească") that gives the root for the name of the country. "Wallachia" comes from "Valach" or "Vlach", a Germanic term (used also by Slavic and other people) to name the "foreigner", the non-German (which also gave Walloon and even Welsh), more specifically the Latin, then the neo-Latin speakers in general, that is - in Eastern Europe - the Romanians. The people themselves didn't called themselves Wallachian, but "români" nor their country Wallachia, but "Tara Romaneasca", meaning Romanian Land. In opposition to Moldavia, it was called "Muntenia". In official medieval documents written in Slavonic and Greek, Wallachia was sometimes called "Ungro-Vlahia" (Wallachia close to Hungary) while Moldavia was called "Moldo-Vlahia" (meaning the Moldavian Wallachia). The unification of Wallachia and Moldavia in 1859 resulted in a new state called Romania, with the capital in Bucharest, that is the former Wallachian capital. Besserabia was added only between 1918-1940, and 1941-1944.

• Romanian and Moldavian - is there a difference? The situation is similar to the one described above, but also more complicated by the fact that there are here two Moldova-s/Moldavia-s (one in Romania and one outside it). While Wallachian capital became the capital of Romania one might imagine a sort of conquest of Moldavia by Wallachians or something similar: it is not at all the case. The first ruler of the unified Romania was a Moldavian nobleman, and Moldovan/Moldavian nobility and elites were very present in ruling Romania. But, like in all cases of new national states in the 19th century, the trend of centralization has produced (like in Italy and Germany) a process of h*m*genization in which the capital and its region became the cultural focus. The Moldavian capital, Iaşi, could have hardly become the capital of the new state, because, as a result of Russian conquest of Besserabia, it was situated almost on the very Russian frontier. - After the independence of the (former soviet) Republic of Moldova in 1991 the terms "Moldavia/Moldova/Moldavian/Moldovan" are used more and more for that region, and sometimes in contrast to Romania/Romanian, to the point where foreigners (that is: frankly ignoring the history of the small principality of Moldavia) may imagine Moldavia/Moldavians as something different or exterior to Romania/Romanians. - While only the accent ever separated the languages of Wallachia and Moldavia, the Russian occupation of the Moldavian region east of the Prut river resulted in a process of Russification of the language (and colonization of the territory) there, which played both as a cause and as an argument in favor of the propagandistic idea of the existence of a Moldavian language different from Romanian. During most of the 19th century, when Romanian underwent a process of re-Latinization & modernization under the influence of French, Besserabia was under Russian rule. But that process affected all speakers of Romanian of the cultural elites, while the majority of the people was not influenced either way (not to mention that Tsarist elites were also speaking French). Things changed after WW2, when the creation of a soviet Moldavian republic was doubled by an effort of proving that a specific nation with a specific language different from those of Romania corresponded to that republic. The practical result was not a difference between "Moldavian" and Romanian, but a poorer quality of the spoken Romanian and a less number of people speaking it, as many were deprived of access to proper schooling in their own language in favor of Russian.

The OP says: "Since they are two adjacent countries with basically the same language and ethnicity, I assume they were once a part of the same nation? If yes, what nation were they united under? For what period of time were they united before splitting? How did the split occur?"

I think that the question raised and the Tom Au's answer suffer from a confusion that needs clarification. It's a confusion about the very terms involved (Moldavia, Moldova, Romania) and even about the historical background.

First, it is not evident that two states that share the same ethnicity must have been in the past part of the same unified state. It is the unified modern state that may be based on common ethnicity of former separate states. Such is the case with some European states, like Italy and Germany. Romania follows this trend and was created in the same period through the unification of Wallachia and Moldavia. On the other hand, the modern states of Romania and Moldova were at some point united; that is, present Republic of Moldova covers a territory that in the past was part of the principality of Moldavia which itself became part of Romania.

From the context I think the OP is referring not only to Romania and Republic of Moldova, but also to Wallachia and Moldavia, and that there is a confusion between them. Historically we have four state-entities involved in this discussion: the older principalities (or voievodate-s) of Wallachia and Moldavia, the Romanian modern state (on the territories of Wallachia and Moldavia, of the Principality of Transilvania, and other territories of Austria-Hungary and Ottoman Empire), and the present independent Republic of Moldova (a former Soviet republic).

Therefore I will list the main historical data that I hope will both clarify the question and provide an answer as to why the states involved became separated at some point. Also, the maps in the posted links will greatly help clarifying things.

Romania is the name of the modern state created with the 19th century unification of two older separate entities: the "principalities" of Wallachia and Moldavia, which in the 18th century started being called the Danubian Principalities. - Only in 1918 it integrated also Transilvania, then part of Hungary, to cover largely the territory of the three principalities that in 1600 had been for a very short period under the personal union of the Wallachian prince Michael the Brave.

[By Anonimu at the English language Wikipedia, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=706080]

Wallachia and Moldavia appeared on the map of Europe as separate entities ruled by separate dynasties, but they were very similar:

• shared the same language and the same Orthodox Christianity;
• started as vassals to the kingdom of Hungary (who was instrumental in the very creation of the principality of Moldavia during their fight against the Mongols);
• gained independence in the 14th century, largely enjoyed independence in the 15th century, but later had great difficulties in keeping their full independence against their stronger neighbors; they counted on constantly switching allegiance between Hungary, Poland and Ottoman empire to safeguard independence and became clearly dominated by the Ottoman empire in the 16th century when the Hungarian and Polish influence receded;
• had the same type of ruling system that imitated the Byzantine rule; the monarch (called in both principalities Voievod or Domn - from Latin, Dominus) was seen in the catholic West rather as a prince than a king, but exercised in fact the same Byzantine-styled absolute authority over his nobles as other rulers of the Orthodox world, the tsars of Bulgaria, Serbia and Russia).
• the two countries started to irreversibly lose independence in the 16th century, but were never dissolved; they were part of the Ottoman Europe, but (unlike Bulgaria, Serbia or part of Hungary) they were never integrated as a governorate into the empire as such (excepting for Budjak in Moldavia and the main Wallachian ports on the Danube), their internal organization was not changed, Orthodox Christianity was not hindered in their territories - where, remarkably, preaching Islam was forbidden, and no Turkish colonization ever occurred - , and they continued to be governed by the local dynasties until the 18th century, when the intervention of Russia and Austria tempted again the local rulers to switch allegiance, which convinced the Turks to replace Romanian dynasties with Greek Byzantine dynasties from Contantinoples (the Phanariotes); these Greek ruling families shared the same religion, had already intermarried with the nobility of the two countries, and largely adopted the local language; unlike previous local rulers, the same Phanariote princes (in separate periods) or members of the same families ruled in both countries - thus creating a trend that continued after them, which contributed considerably to bringing the two states even closer together; they became active in the Greek (as well as Romanian) Enlightenment and in the Greek national movement; the Greeek war of independence started in part on the territory of the Romanian principalities; as a result, the Ottomans replaced back the Greeks with Romanian rulers (after 1821).

[By Aoleuvaidenoi - Own work, Public Domain, https://commons.wikimedia.org/w/index.php?curid=12493021]

Republic of Moldova (sometimes simply called Moldova) is a recent state which became independent at the fall of the Soviet Union largely on the territory between the rivers Prut and Dniester that was part of the principality of Moldavia and was occupied in 1812 by the Russian empire. This territory started to be called Besserabia when it became disputed and caught the attention of European geographers, but the name doesn't reflect any previous separation from the rest of Moldavia. Unlike the previous Turkish domination, Russian occupation meant full integration into the empire with the creation of a governorate, which didn't mean local autonomy as much as a politics of Russification and colonization. (The main part of the country, the capital, most of the main cities and the main population were on the western side of the Prut river and by the unification with Wallachia became a new state: The United Principalities of Moldavia and Wallachia, as a personal union in 1859, full union in 1862, and then the Kingdom of Romania in 1881.) After the First World War and the Bolshevik Revolution, Romania occupied the territory of the Besserabia Governorate. Soviet Union took it back after World War Two and created the Moldavian Soviet Socialist Republic.

The very term Moldova needs some clarification: "Moldova" is simply the name of "Moldavia" in Romanian language, which is spoken both in Romania and the Republic of Moldova. Romanians commonly use the term "Besserabia" to refer to the Republic of Moldova and use the term Moldova to name the eastern part of Romania. Romanian officials prefer the term "Republic of Moldova" instead of just "Moldova" to name their eastern neighbors, but in English "Moldavian" and "Moldovan" are starting to be used both in relation to the present republic of Moldova. "Moldova" is also starting to be used in English for the whole historical region and namely the part of Romania that in English was traditionally called "Moldavia". There is a disambiguation page on Wikipedia.

[ By Spiridon Ion Cepleanu - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=17314546]

And now I'll try to formulate an answer to the initial question "how the two have become separate in the first place".

Why the two older principalities of Wallachia and Moldavia have existed for so long as separate states? Because they had been created separate, just like the German or the Italian states. They might have been united earlier if they had been stronger. (In 1600 a Wallachian prince was strong enough to create a personal union for a short moment.) Keeping their relative independence was already a task that took all available resources for hundreds of years. When the immediate pressure from powerful neighbors like Russia, Austria and Turkey receded through the intervention of France and England and through the logic of European equilibrium (after the Napoleonic wars) new conditions for independence and unification have appeared. These conditions improved further after the Crimean War, when Turkish and Russian intervention was replaced by the more distant French and British influence, which opened the path to unification.

Why Romania and the eastern part of Moldova (Besserabia) were separated in the first place? Because at the moment when the modern Romanian state was created by the unification between the Wallachia and Moldavia (1859), the present territory of the Republic of Moldova (the eastern part of Moldavia) had been already taken by Russia (1812). Unlike other territories under Russian rule, namely Poland or Finland, this was not really an entire country and was not treated as such, but underwent a process of colonization and Russification. As an ally to the WW1 victors, Romania regain control of this territory in 1918-1919 but then lost it again to URSS in 1945.

As for the question why are they not united now, there is a question with rather good answers here.