Cetatea Soroca a fost construită pe locul unei fortăreţe genoveze
Cetatea Sorocaeste o cetate moldovenească din secolul XV, întemeiată de Ştefan cel Mare, în faţa vadului peste Nistru, pe locul unei vechi fortăreţe genoveze, Alciona. Cetatea a fost reconstruită ulterior de către Petru Rareş. care a reconstruit zidurile în piatră.
La 12 iulie 1499, la Curtea Domnească de la Hârlău, în sala de tron, boierii din Sfatul Domnesc adeveresc adeverind biruinţa lui Ştefan cel Mare, pacea cu regele polon Ioan Albert. Printre boierii Ţării Româneşti Moldova se aflau Toader şi Negrilă, starostii de Hotin, Ieremia şi Dragoş, pârcalabii de Neamţ, Luca Arbore, portarul de Suceava, Ivanco şi Alexa, pârcălabii de Orhei, Coste, pârcălab de Soroca.
La 14 septembrie 1499, Ştefan cel Mare încheie un tratat de ajutor reciproc cu marele duce de Lituania Alexandru, unde ca şi-n documentul precedent este menţionat pan Coste, staroste de Soroca.
Câteva izvoare istorice menţionează ridicarea unor cetăţi pe Nistru la vaduri, din lemn sau din piatră, în scaunul cărora se aşează pârcălabi şi mari căpitani de Hotin, Soroca, Orhei, Tighina şi Cetatea Albă. Se presupune că la Soroca a fost înălţată o cetate din lemn şi pământ, a unei palănci sau poate chiar posade în primul sfert al secolului XV, dar cu o primă menţiune documentară la 12 iulie 1499 prin primul ei pârcălab, Coste.
