In schimb, polonii se angajau sa nu-i permita lui Aron sa se apropie de hotarele Moldovei. Pentru a incerca sa-si recupereze tronul, Aron a trecut in Transilvania. Acesta este motivul pentru care Stefan se decide sa atace cetatea Chilia, aceasta poarta a Moldovei care era in mana ungurilor. Prin cucerirea cetatii, Stefan urmarea nu doar un scop politic (o lovitura data sustinatorilor lui Aron) ci si un scop militar si economic. Chilia era impreuna cu Cetatea Alba cea mai buna aparare impotriva turcilor. Ea reprezenta si un antrepozit comercial de prima mana pentru ca aici se concentrau marfuri romanesti, unguresti, polone si rasaritene, iar vama luata de pe aceste marfuri ar fi constituit un important venit pentru vistieria Moldovei. In 1465 Stefan va reusi sa cucereasca Chilia. Intre timp el reia de la poloni cetatea Hotinului.
Stefan a trebuit, in prima parte a domniei sale, sa plateasca tribut lui Mehmed al II-lea, cuceritorul Constantinopolului. Primul lucru care se impunea, in campania impotriva turcilor, era scoaterea Munteniei din zona acestora de influenta. Din acest motiv indepartarea din scaun al lui Radu cel Frumos era inevitabila, si Stefan va urmari acest lucru timp de patru ani de zile, din 1470 pana in 1474.
Conflictul a inceput prin pradarea si arderea Brailei, cel mai insemnat port muntean. Ca o replica, turcii au trecut Nistrul in acelas an si au pradat orasele din aceasta zona. Actiunea lor de cucerire nu a avut insa succes deoarece Stefan fusese avertizat. Pentru a rezolva problema pe care o avea cu Radu cel Frumos, Stefan a hotarat sa puna in locul acestuia un protejat de-al sau, Basarab cel Batran.
