The names of Moldavia and Moldova originate from the historical state of Moldavia, which at its greatest extent included eastern Romania (Western Moldavia), Moldova, and parts of south-western and western Ukraine.

One of the existing theories is that Moldavia/Moldova was named after the Moldova River, which is a Slavic name,^[1] derived from Slavic mold-, "spruce, fir".^[2][3] A. I. Sobolevskij derived it from *moldu, "tender, soft, young".^[4] The ending -ov(a)/-av(a) is a common Slavic suffix used in appelatives and proper names.^[5] -ova denotes ownership, chiefly of feminine nouns. There is significant Slavic influence on Romanian.

The myth, included in works of Grigore Ureche (1590–1647), Miron Costin (1633–1691) and Dimitrie Cantemir (1673–1723), but given varying levels of credibility by these, was that the hunter Dragoș from Maramureș (the founder of Moldova) One myth, given different levels of credence by Ureche, Miron Costin, and Cantemir, was about a place-name: Moldova. Other theories is that it is derived from old German Molde, meaning "open-pit mine",^{[citation needed]} or the Gothic Mulda meaning "dust", "dirt" (cognate with the English mould), referring to the river.^{[citation needed]}

The short-lived capital of Moldova, Baia in the Suceava County, was called Stadt Molde in a 1421 German document.

The original and short-lived reference to the region was Bogdania, after Bogdan I, the founding figure of the principality.^[6] Polish historian Ilona Czamańska [pl] states that, "according to the tradition of local chroniclers, the first Moldavian prince who agreed to pay tribute to the Ottomans was Bogdan III, who reigned in the years 1504–1517,"^[7] and notes that "this was [later used] to explain the Turkish name of Moldavia — Bogdania. In fact, this name is of Tatar origin and was used long before Bogdan III was born. It is undoubtedly associated with Bogdan I," the first voivode of Moldavia in the 1360s.^[8] It is this name that voyager Richard Hakluyt used for Moldavia in his writings in the late 16th century.^[9]

The term "Black Wallachia" (Romanian: Valahia Neagră), in Turkish Kara-Eflak, was another name found used for Moldova in the Ottoman period.^[10] It derived from Bogdan I of Moldavia; in Ottoman Turkish usage his state was known as Kara-Bogdan (Romanian: Cara-bogdan)^[11] and Bogdan-Eflak, "Bogdan's Wallachia".

Before 1812 the territory of the modern Republic of Moldova was usually called Eastern Moldova, Eastern Lowlands, Dniester-Prut, Bendery (for the largest town) or Orhei (for the largest town in the centre). After the entire eastern part of the region, between the Pruth and the Dniester, was ceded by the Ottomans to Russia in the 1812 Treaty of Bucharest, the Russians used the name Bessarabia for its new acquisition.^[12] though this name had formerly only been applied to the southern parts of this territory, what is now called Budjak, it quickly became associated with the whole territory. After the establishment of the Moldavian SSR in the 1940s the new republic started to be unofficially called Moldavia. In 1991 that name was adopted as official name, with Romanian-language variant Moldova quickly become the preferred spelling.