Położona na równinach między Prutem a Dniestrem kraina od setek lat przyciągała osadników i wojowników. W starożytności osiedlili się tu Celtowie i Germanowie, potem Dakowie. Po nich przyszli Rzymianie, którzy przejęli kontrolę nad Mołdawią, ale nie uczynili jej prowincją Cesarstwa. Gdy ich imperium upadło, przyszli koczownicy Wielkiego Stepu: Scytowie, Hunowie, Goci i Pieczyngowie, a po nich Mongołowie. Tych ostatnich przegnali na początku XIV wieku królowie węgierscy, którzy wpadli na pomysł, że ufortyfikują Mołdawię, aby powstrzymywała ona najazdy koczowników na ich państwo ze wschodniej strony. Pomysł nie okazał się jednak trafiony. Wołochowie – jak nazywano mieszkańców dzisiejszej Besarabii i Mołdawii – zapragnęli samodzielności i zdecydowali się na politykę lawirowania między potężnymi sąsiadami. W 1387 roku hospodar Piotr I Muszatowicz przyjechał do Krakowa i złożył hołd królowi Władysławowi Jagielle i królowej Jadwidze, co oznaczało, że jego państwo staje się lennem Polski, a Jagiełło – jego faktycznym władcą. Monarcha, zajęty scalaniem Litwy i Polski w jeden organizm państwowy, nie miał jednak czasu zająć się sprawami nowego terytorium. Następny hospodar, którym był Roman I, uznał się za władcę niezależnego i rozpoczął ekspansję terytorialną, dochodząc z rycerzami aż do brzegów Morza Czarnego. Ambitny władca popadł jednak w konflikt z bojarami, a ci szybko go zdetronizowali. Sukcesję po nim objął syn Aleksander, któremu historia nadała przydomek Dobry. Był on zdania, że rozwój młodego państwa wymaga pokoju, dlatego pojechał do Krakowa i wzorem dziadka ponownie złożył hołd królowi Jagielle. Był pewien, że potęga Polski osłoni Mołdawię przed zakusami króla węgierskiego i przed najazdami tatarskimi. Aby dać dowody lojalności względem Polski, Aleksander Dobry wysłał oddział rycerzy, którzy wsparli króla Jagiełłę w bitwie pod Grunwaldem. Od tego momentu jeszcze przez prawie ćwierć wieku Mołdawia była lennem Polski, osłanianym jej rosnącą potęgą. Sam Aleksander Dobry wykorzystał ten czas, aby urządzić swój kraj: rozbudował porty nad Morzem Czarnym, wzniósł i umocnił twierdze, wybudował szlaki komunikacyjne, fundował cerkwie i monastery.
Sojusz z Drakulą
Zmiana nastąpiła dopiero w 1430 roku. Wówczas Świdrygiełło, najmłodszy brat Jagiełły, uwięził polskiego króla w Wilnie, co natychmiast wywołało ekspedycję karną polskich rycerzy. Między braćmi wybuchła kłótnia o litewski tron. Jagiełło, który od czasu unii w Krewie był formalnie królem Polski i Litwy, powierzył tron Świdrygielle, licząc, iż po jego śmierci władzę obejmie jeden z synów Jagiełły, litewski kniaź nie miał bowiem dzieci. Tak rozpoczęła się wojna domowa w Polsce, nazwana przez historyków wojną łucką – od nazwy miasta, wokół którego toczyły się główne boje. Aleksander Dobry, mamiony obietnicami Świdrygiełły, który obiecał mu niezależność, przyłączył się z rycerzami do jego armii. Jego wojsko ruszyło w stronę Łucka, po drodze dokonując zniszczeń Rusi Czerwonej. Król Jagiełło wysłał przeciwko niemu oddział wojskowy, który rozbił Mołdawian, a Aleksandra Dobrego zmusił do ucieczki. Było prawdopodobne, że Polska wyśle ekspedycję wojskową, aby pochwyciła Aleksandra i przywiozła go do Krakowa, gdzie poniósłby karę za nieposłuszeństwo. Tak się jednak nie stało. Aleksander Dobry wkrótce zmarł, a Mołdawia pogrążyła się w kryzysie wywołanym walkami jego dzieci i wnuków o władzę. Trzy lata później zmarł król Jagiełło, a skłócony z nim brat przegrał wojnę domową i ostatecznie uznał zwierzchność jego syna – Kazimierza Jagiellończyka. Pretendenci do mołdawskiego tronu musieli więc poszukać protektora, a do wyboru mieli Polskę albo Węgry. W ciągu następnych 25 lat trzech kandydatów do mołdawskiego tronu złożyło hołd lenny Kazimierzowi Jagiellończykowi, a dwóch – królom węgierskim. Poszły za tym ustępstwa terytorialne. Rzeczpospolita dostała Chocim, a Węgry – port w Kilii nad Morzem Czarnym. W końcu, w 1456 roku, inną strategię przyjął hospodar Piotr III Aron. Chcąc uniezależnić się zarówno od Polski, jak i od Węgier, zawarł sojusz z sułtanem tureckim. W zamian za opiekę zgodził się płacić mu haracz. Wtedy do gry, z inspiracji polskiej, wtrącił się hospodar Wład III Palownik, zwany Drakulą. Znany z okrucieństwa władca usunął z tronu Piotra III, a osadził tam Stefana, któremu nadano przydomek Wielki i który w historii zapisał się jako najwybitniejszy mołdawski władca.
Polska, Węgry i Turcja
Stefan Wielki obejmował tron w momencie, gdy apetyt na jego kraj ostrzyły sobie zarówno Rzeczpospolita, jak i Węgry, Turcja oraz Rosja. Stefan zbudował silną i nowoczesną armię, która przez 20 lat z sukcesem stawiała czoło wszystkim wrogom. Najpierw pokonał króla Węgier Macieja Korwina, potem obronił swój kraj przed najazdami tatarskimi, w końcu stawił czoła najazdowi tureckiemu, odnosząc świetne zwycięstwo pod Vaslui. Równocześnie dbał o rozwój wewnętrzny kraju: umocnił dotychczasowe twierdze, założył kilka nowych miast, w tym obecną stolicę Mołdawii – Kiszyniów. Fundował cerkwie i monastyry, dbając o to, aby powstały przy nich szkoły.
W 1481 roku Turcy zmusili Stefana do płacenia haraczu, a trzy lata później odebrali mu siłą porty czarnomorskie, w tym Białogród nad Dniestrem, który uchodził za „klucz do ziemi polskiej, ruskiej i tatarskiej". Zajęcie Białogrodu utrudniło polski handel wschodni, który ze Lwowa szedł właśnie w kierunku Morza Czarnego. W tej sytuacji Stefan Wielki, który miał złe relacje z Węgrami, zwrócił się o pomoc do Polski. 15 września 1485 roku przyjechał do Kołomyi i tam złożył hołd lenny Kazimierzowi Jagiellończykowi. Polski władca zgodził się, by Stefan – już jako jego poddany – objął mołdawski tron. Gwarantem tej obietnicy była armia licząca kilka tysięcy polskich żołnierzy pod dowództwem starosty głogowskiego Jana Karnkowskiego. Połączone siły polsko-mołdawskie w listopadzie 1485 roku. odniosły zwycięstwo nad Turkami. Od tej pory panowanie w Mołdawii stało się jednym z głównych celów jagiellońskiej polityki, której nadrzędnym priorytetem było zatrzymanie tureckiej ekspansji.
Królewicz Jan Olbracht rozpoczął przygotowania do wyprawy wojennej przeciwko Turcji, która miała ruszyć w 1487 roku. Sułtan, który nie chciał konfrontacji z Polską, uciekł się do fortelu: zawarł sojusz z chanem krymskim, który wysłał czambuły, aby pustoszyły południowo-wschodnie rubieże Rzeczypospolitej. W rezultacie królewicz Olbracht musiał stawić czoła Tatarom. 8 września 1487 roku. rozbił ich w bitwie pod Kopystrzyniem. 4 lata później wojska polskie odniosły drugie wielkie zwycięstwo nad Tatarami w bitwie pod Zasławiem. Zagrożenie tatarskie zniknęło, ale zajęte wojska polskie nie mogły wejść do Mołdawii. A o to właśnie chodziło sułtanowi. W 1487 roku. zmusił Stefana Wielkiego, aby poddał się i złożył mu hołd.