În 1457, când a urcat pe tron, Ştefan cel Mare s-a văzut înconjurat de vecini agresivi şi expansionişti. Pe lângă otomanii din sud, în vest era Ungaria, Polonia la nord, iar ambele ţări voiau să domine Moldova şi să obţină controlul asupra rutelor comerciale profitabile dintre Marea Neagră şi Europa Centrală. Strategia lui Ştefan, pe care a aplicat-o cu un succes răsunător, a fost aceea de a-şi întărâta duşmanii unul împotriva celuilalt. A plătit tribut otomanilor, dar numai atunci când a fost avantajos (a încetat să o facă între 1473 şi 1488) ; l-a recunoscut pe regele Cazimir al Poloniei ca suzeran atunci când a părut înţelept, de pildă în 1459 şi în 1485 ; şi a recurs la arme când celelalte mijloace dăduseră greş. A avut câteva succese militare de seamă : în 1467, în bătălia de la Baia, când a învins armata cotropitoare a regelui Matei Corvin al Ungariei, victorie care a marcat ultima încercare de proporţii a unui rege maghiar de a-şi impune voinţa în Moldova ; şi în 1475 la Vaslui, când a înfrânt o mare armată otomană condusă de guvernatorul (beylerbeyi) Rumeliei. De asemenea, le-a solicitat în repetate rânduri puterilor creştine din Europa Centrală şi de Vest să i se alăture într-o coaliţie care să stăvilească înaintarea otomanilor, iar pentru eforturile sale papa Sixt al IV-lea (1471-1484) i-a conferit titlul de „Atlet al lui Hristos”, însă totul a fost zadarnic. În ultimii ani ai domniei sale presiunea otomană a fost neînduplecată şi, deşi armatele sale au mai şi învins, cum s-a întâmplat în 1497 împotriva regelui Cazimir, nu şi-a făcut iluzii că i-ar fi putut înfrânge pe otomani pe calea armelor. Drept urmare, înainte să moară, i-a cerut fiului său, Bogdan, să încerce să aibă o relaţie bună cu ei, aceasta fiind singura modalitate de a menţine independenţa Moldovei.

Bogdan al III-lea (1504-1517) şi urmaşii lui au perpetuat o independenţă precară până în 1538, când sultanul Suleiman I (1520-1566) a început să exercite un control mai ferm asupra Moldovei. În acel an sultanul a alungat de la tron un domnitor ce nu prezenta încredere, pe Petru Rareş (1527-1538, 1541-1546), şi l-a înlocuit cu maleabilul Ştefan Lăcustă. Noul domnitor l-a recunoscut pe Suleiman drept suzeran, confirmând astfel statutul de vasal al Moldovei.

Relaţia juridică ce a evoluat între principate şi statul otoman în secolele al XV-lea şi al XVI-lea s-a datorat în aceeaşi măsură pragmatismului şi teoriei legale otomane, cât şi condiţiilor politice şi sociale din Moldova şi Valahia şi circumstanţelor internaţionale de la acea vreme. Din perspectiva legii islamice a naţiunilor, pe care o urmau otomanii, principatele se aflau într-o zonă intermediară, între dar al-harb („domeniul războiului”), teritorii contestate de statul musulman şi de duşmanii săi, şi dar al-Islam („domeniul Islamului”), teritorii în care locuitorii erau supuşi unui conducător musulman şi legii islamice. În secolul al XVI-lea, principatele în mod cert nu mai făceau parte din prima categorie, dar nici nu intraseră în cea de-a doua. Unii istorici le-au plasat în dar al-sulh („domeniul păcii”) sau în dar al-‘ahd, teritoriu dobândit de conducătorul musulman prin tratat ; alţii, în conformitate cu şcoala juridică hanefită, care predomina în Imperiul Otoman, i-au inclus în dar al-muvâda’a („domeniul armistiţiului”) sau dar al-dhimma („domeniul protecţiei şi al tributului”). E posibil ca ultimii doi termeni să reflecte cu mai multă acurateţe cele două faze principale prin care au trecut relaţiile româno-otomane, anii 1538-1541 reprezentând linia de demarcaţie. La începutul confruntării lor, principatele erau state vasale silite să plătească tribut şi să asigure servicii militare, iar apoi, pe măsură ce relaţiile s-au strâns, sultanul şi-a asumat anumite responsabilităţi faţă de principate, în primul rând aceea de a le proteja.

Aranjamentul creat a permis Moldovei şi Valahiei să evite asimilarea în sistemul politic otoman, aşa cum se întâmplase cu statele creştine de la sud de Dunăre. Diverse ‘ahd-names şi berāts (dispoziţii de numire) din partea sultanilor au acordat principatelor autonomie internă aproape deplină. Astfel, sultanul recunoştea dreptul domnitorului şi al boierilor de a guverna „conform obiceiului” şi interzicea autorităţilor civile şi militare turce sau clerului musulman să se amestece în problemele interne ale principatelor. Sultanul le-a acordat boierilor permisiunea de a-şi alege domnitorul, dar şi-a rezervat dreptul de a le aproba opţiunea şi de a-i oferi noului domnitor însemnele puterii sale. Ca o consecinţă a autonomiei, legile şi sistemul juridic, structura socială, deţinerea de moşii şi relaţiile agrare, viaţa culturală şi intelectuală şi statutul Bisericii Ortodoxe au rămas neschimbate. Însă sultanul a preluat controlul afacerilor externe, interzicându-le domnitorilor să menţină contacte diplomatice cu statele străine sau să încheie tratate cu acestea, şi s-a angajat să apere principatele de atacurile externe.

În ciuda extinderii puterilor lor asupra Moldovei şi Valahiei, sultanii nu le-au ocupat armat şi nu le-au transformat în provincii otomane, aşa cum procedaseră cu teritoriile de la sud de Dunăre, precum cel sârb şi cel bulgar, şi cu centrul Ungariei după 1541. Explicaţia acestei reţineri ţine în primul rând de contactele tot mai bune ale otomanilor cu principatele. În fazele incipiente ale relaţiei lor, la sfârşitul secolului al XIV-lea şi în secolul al XV-lea, sultanii au tins să acorde principatelor o importanţă secundară, orientându-şi atacul major spre vest şi nord-vest. Au părut mulţumiţi să-i împiedice pe domnitori să se alăture coaliţiilor antiotomane. Însă nici unitatea afişată de domnitori şi boieri în momentele cruciale nu a trecut neobservată la curtea otomană, unitate care a descurajat acţiunea militară. Suleiman I, care ar fi vrut să numească sanjakbeys (guvernatori) care să administreze principatele, a fost fără îndoială descurajat să ia o asemenea măsură de natura relaţiilor economice bune cu principatele, care aduceau sume frumoase în vistieriile personale ale sultanului şi apropiaţilor săi, cantităţi indispensabile de alimente la Constantinopol şi provizii de