Les sources historiques (carte de Ptolémée entre autres) mentionnent, depuis près de 2000 ans, quelques villes au bord du Nistre, alors appelé Tyras ; cependant il est encore difficile de dater l’apparition de la ville de Soroca. La théorie la plus répandue est qu’elle fut une escale génoise sur la « route de l’ambre et de la soie » entre la mer Baltique et la mer Noire, construite ici à un emplacement stratégique près d’un gué[1].

Les Génois sont en effet présents sur les bords de la mer Noire depuis le début du XIIIe siècle où l’on retrouve leurs comptoirs à Constantinople, Caffa et Azov. Mais c’est à partir du XIVe siècle qu’ils s’installent à l’embouchure du Nistre, dans la ville de Cetatea Albă (Montecastro), se servant du fleuve comme un axe de communication avec le nord du pays et la Pologne[2].

Soroca, alors appelée Policromia ou Olihonia, faisait partie, avec Hotin (aujourd’hui Khotin en Ukraine), Tighina et Cetatea Albă, des quatre escales fortifiées pour la navigation fluviale sur le Nistre, situées près des quatre principaux gués du fleuve, où passaient alors des bolozanes (chalands fluviaux à rame et voile) convoyant l’ambre et les fourrures de la mer Baltique vers Trébizonde et Constantinople, et dans l’autre sens la soie, les perles, le miel, les épices vers les pays du Nord. Les bolozanes n’avaient pas toujours assez de tirant d'eau pour passer les gués en été, à l’étiage, et il fallait alors débarquer les marchandises et changer d’embarcation, tout en surveillant le gué pour éviter les incursions venues de l’Est. Voie fluviale des Varègues (Vikings de la Baltique) vers l’Empire byzantin, le Nistre était également une frontière entre, à l’Ouest (rive droite), le monde villageois et citadin des populations sédentaires chrétiennes (ici moldaves) vivant d’agriculture et de commerce dans une mosaïque de prés, bocages et forêts, et, à l’Est (rive gauche), le monde des steppes, domaine des Onogoures, Khazars, Pétchénègues, Coumans, Mongols ou Tatars païens (chamanistes) et plus tard musulmans, vivant de campagnes guerrières et d’élevage extensif dans la steppe pontique et jusqu’en Asie centrale d’où ils arrivaient successivement.

C’est pourquoi ces sites, dont Soroca, sont de plus en plus fortifiés par les souverains moldaves : tous sont convoités et fréquemment assiégés par les peuples guerriers des steppes, par le royaume Polono-Lituanien, par l’Empire ottoman et par l’Empire russe (qui, en 1812, finira par tous les annexer)[1].

Il est difficile de dater précisément le début de la construction de la forteresse actuelle, que l’on situe globalement dans la seconde partie du XVe siècle. Le plus souvent, la construction de l’ouvrage de pierre est attribuée à Étienne III le Grand, même si certaines sources laissent sous-entendre que son fils Pierre IV Rareș aurait pu reconstruire ou en renforcer les défenses en 1543. De même, le chroniqueur Moldave Miron Costin laisse planer un doute lorsqu’il évoque « Petru-Vodǎ » à propos de Soroca, nom qui peut faire référence à Pierre IV Rareș, fils d’Étienne III, ou à Petru II (1375-1391), prince de Moldavie bien plus ancien[3].

L’historien et spécialiste N. Bulat penche, lui, pour une construction de la forteresse en plusieurs étapes par plusieurs monarques différents qui lui aurait donné son aspect final actuel[1].

Quoi qu’il en soit la première mention d'un ouvrage défensif est clairement attesté en 1499 par le "pîrcălab" de la cité (gouverneur militaire, voir les offices des principautés roumaines)[1].