Сорокская крепость была построена Штефаном Великим в последней четверти XV века. Так гласит местная традиция, которая объясняет её название тем, что господарь установил «сорок» (срок возведения крепости). В 1499 году документального упоминается Косте — первый пыркэлаб крепости. Крепость Сорока была построена как оборонительное укрепление против хищных татарских орд, которые через днестровские переправы вторгались в Молдову. Сорока не была большой крепостью с двумя рядами стен, как Сучава, Четатя Албэ или Хотин, а только небольшим укреплением, замком для укрытия стражников против татар.

Некоторые историки, в том числе Дмитрий Кантемир, Константин Стамати, Замфир Арборе и Николае Йорга, считают, что Сорокская крепость была построена на месте бывшей генуэзской фактории Ольхиония, где складировались товары, привезенные из Подолии. Ольхиония будто бы было укрепленным поселением на пути из Четатя Албэ в Сучаву. Но на данный момент нет археологических доказательств в поддержку этой гипотезы.

Археологические исследования обнаружили вокруг города поселения, характерные для культуры Триполье-Кукутень, бронзового века, эпохи раннего железа и другие, вплоть до эпохи средних веков, но следы древней колонии Ольхиония (около 500 лет до н. э.) не были идентифицированы, как не были найдены и следы древней крепости даков Саргус (называемой еще Саргидава, Крахита или Крахидава), которые, по мнению некоторых историков прошлых веков, находились в этой зоне.

В конце XVII века, во время пребывания в крепости гарнизона из 2000 польских солдат, были сделаны ряд изменений. К стенам были пристроены еще 13 помещений для хранения пороха, а над ними — комнаты для проживания. Интервалы между зубцами были закрыты и оставлены только отверстия для легких ружей. Для польских солдат были построены казармы за пределами крепости, и вся площадь окружена земляным валом и рвом.

Крепость Сорока в качестве самой восточной точки обороны Молдовы на протяжении своей истории была ареной самых ужасных вторжений. Здесь, у подножия её стен, проходили жестокие сражения.