Byzantine influence is evident during the 5th to 6th century, such as the site at Ipotesti-Cândesti, but from the second half of the 6th century and in the 7th century Slavic peoples settled and populated much of the Balkans. Wallachia was under the control of the First Bulgarian State from its formation in 681 until approximately the Hungarian conquest of the Carpathian basin at the end of the 10th century.
With the decline and subsequent fall of the First Bulgarian Empire to Byzantium (in the second half of the 10th century up to 1018), Wallachia came under the control of the Pechenegs (a Turkic people) who extended their rule west through the 10th and 11th century, until defeated around 1091, when the Cumans of southern Russia took control of the lands of Moldavia and Wallachia. Beginning with the 10th century, Byzantine, Bulgarian, Hungarian sources, and later Western ones, mention the existence of small states populated possibly also by Romanians under leaders known as knyazes (Slavonic: prince, ruler) and voievods (Slavonic: military leader) - at first in Transylvania, then in the 12th-13th centuries in the territories east and south of the Carpathian Mountains. A specific characteristic of Romanian history from the Middle Ages to modern times is that Romanians lived in three adjacent principalities - Wallachia, Moldavia and Transylvania, separated by the Carpathian mountains.
During the solar eclipse of 21 April 1186, the Byzantines successfully attacked the Vlachs, many of whom fled north of the Danube, making contact with the Cumans. Thus, when the Vlachs returned with their Cuman allies, they found the region undefended and regained not only their old territory but the whole of Moesia, thus uniting Vlach and Bulgarian lands. The lands between the Haemus and the Danube were now lost to the Byzantine Empire. The Vlach-Bulgarian Rebellion was a revolt of the Vlachs and Bulgarians living in the Byzantine Empire. It began at the turn of the yeare 1185/1186 and ended with the creation of the Second Bulgarian Empire, ruled by the Asen dynasty. In 1185, two noble brothers from Tarnovo named Peter and Asen led a Bulgarian revolt against Byzantine Greek rule and declared Tsar Peter II (Theodore Peter) as king of the reborn state. The following year, the Byzantines were forced to recognize Bulgaria's independence. Peter styled himself "Tsar of the Bulgars, Greeks, and Vlachs"
In 1241 known as the Mongol Khanate of the Golden Horde destroyed the Cuman rule and attacked Poland, Bohemia, Hungary, and Bulgaria. The Mongols had control of Moldavia, most of Wallachia remaining outside their authority, while Transylvania was subjected to many attacks. The removal of pressure exerted from Hungary and Bulgaria no doubt helped the assertion of the Romanian feudal states.
One of the first items of documentary evidence of Romanian voivodes is of Litovoi in 1272 who ruled over land each side of the Carpathians, including Fagaras in Transylvania, and refused to pay tribute to the Hungarian King Ladislaus IV. His successor was his brother Barbat (1285-1288). The continuing weakening of the Hungarian state by further Mongol invasions (1285) and internal disputes opened the way for the process of unification of the Romanian political formations independent of the Hungarian kings. The formation of the Romanian state happened when Basarab I (1310-1352), son of Tihomir, united the Romanian voivodes either side of the Olt, creating a feudal state based at Câmpulung. He extended his lands to comprise those to be known as Wallachia together with the Banat of Severin, Fagaras, southern Moldavia, the Danube Delta, and the lands between the Prut and Dniester which were to be later known as Basarabia. After Basarab's death his son Nicolae Alexandru ruled Wallachia (1352-1361), followed by his son Vladislav I (1364–1377).
Cumans, also called as Polovtsy, was the European name for the Western Kipchaks, a nomadic West Turkic tribe living on the north of the Black Sea along the Volga. The Cumans invaded southern Ukraine, Moldavia, Wallachia, and part of Transylvania in the 11th century and then continued their plundering of the Byzantine Empire, Hungary, and Kievan Rus'. In 1089, they were defeated by Ladislaus I of Hungary. They were allied with the Vlachs (Romanians) and the Bulgarians during the Vlach-Bulgar Rebellion, being victorious in fights against the Byzantine Empire. They were defeated by Vladimir Monomakh in the 12th century and crushed by the Tatars in 1238. Many took refuge in Hungary, Bulgaria, and the Byzantine Empire. After many clashes with Hungarians, they eventually fled Hungary to join others in Bulgaria. A large segment of Cumans were re-invited back to Hungary and subsequently led the revolt that founded Wallachia. The Cumans from what is now Russia joined the khanate of the Golden Horde.
In the 13th century, the Western Cumans became Catholic Christians, while the Eastern Cumans converted to Islam. The Catholic "Diocese of the Cumans", founded in Milcov in 1227 and including what is now Romania and Moldova, retained its title until 1523. While the Cumans were assimilated, their name can still be seen in placenames such as the city of Kumanovo in Macedonia, Comanesti in Romania and Comana in Dobruja. Toponyms of Cuman language origin can be found especially in the Romanian counties of Vaslui and Galati, including the names of both counties.