Генуэзцы обосновались на территории современной Балаклавы в 1343 году. В середине XIV века на горе Кастрон появились первые крепостные укрепления. Судя по всему, по северному склону это был ров и вал, укреплённый частоколом, а с северо-востока была устроена каменная башня с воротным поездом. Следы этих первоначальных сооружений сохранились на северном склоне горы. Однако в 1354 году ордынский хан Джанибек взял крепость и сжёг существовавшие к тому времени практически все строения.

После заключения мирного договора гора с остатками укреплений была возвращена генуэзцам, и крепость была отстроена заново. На Крепостной горе был построен Город Святого Николая (Верхний город), где расположилась административная часть крепости и Город Святого Георгия (Нижний или Внешний город), в котором жили простые горожане.

В начале 1423 году крепость была захвачена феодоритами. Однако, вскоре, в 1424—1425 годах, Генуэзцы отобрали крепость у феодоритов, и в целях продолжения военных действий, те основали неподалёку свою крепость Каламиту, а генуэзцы поспешили укрепить Чембало. Но в 1433—1434 Чембало вновь была захвачена феодоритами. Осада крепости увенчалась успехом, почти все осаждённые феодориты погибли. В 1460-х годах укрепления Города святого Георгия были перестроены, а в юго-восточном углу была воздвигнута цитадель с мощной башней-донжоном, которая находилась на одной из самых высоких точек.

В 1475 году Чембало захватили турки. В крепости, получившей название Балык-юв («Рыбье гнездо»), был размещён турецкий гарнизон, а позже здесь отбывали наказание провинившиеся перед султаном крымские ханы.