Cetatea Sorocii este menționată pentru prima oară într-un document de la 1499. Cercetările istorice atestă că însuși Ștefan cel Mare ordonase ridicarea pe malurile rîului Nistru a unei fortificații pe locul unei străvechi așezări genoveze (Alciona), care să fie construită în întregime din lemn și împrejmuită de văi adînci din pămînt bătătorit. Mai tîrziu Petru Rareș dori să o întărească cu ziduri masive din piatră. Potrivit mărturiilor istoricului Grigore Ureche, cetatea din Soroca suferise distrugeri grave ca urmare a năvălirilor tătarilor și turcilor.
Faptul este confirmat de alți doi istorici, Miron Costin și Ion Neculce. Construcția fusese concepută pentru apărarea granițelor Moldovei, de la Nistru pîn-la mare, dispre Răsărit; în timp ce garnizoanele de la Hotin și Tighina trebuiau să asigure apărarea dispre Nord. Dar odată cu constituirea Imperiului Otoman (prin căderea Bizanțului la 1453), întreaga peninsulă balcanică, regiunile și ținuturile de pînă la Nistru căzuseră ca pradă militară în mîinile turcilor, inclusiv Soroca.
Același Petru Rareș, după ce recucerise teritoriile de la hotarele de est ale Moldovei, ordonase reconstrucția integrală și restructurarea cetății. Lucrările fură efectuate în termen destul de scurt, din 1543 pînă în 1546. Fortăreața este configurată în plan circular cu diametrul de 40 de metri. Pe laturile extreme se înalță 4 turnuri monumentale. Fiecare turn are trei etaje. În acestea se aflau cazărmile militarilor, depozitele de arme și provizii. Restaurarea părților deteriorate a fost executată recent, astfel încît întreaga structură a complexului apare destul de bine conservată.
Sub privirea vizitatorului care o observă de pe malul opus al rîului aceasta se înalță, impozantă și măreață, cu cele 4 turnuri retezate în aer liber. Amplul parc natural care o împrejmuiește face această priveliște și mai solemnă, și mai sugestivă.