Согласно традиционной версии эту православную церковь построил один из первых консулов Чембало по имени Симон дель Орто. Об этом свидетельствует надпись на камне «1357, в день сентября, начата эта постройка во время управления скромного мужа Симоно дель Орто, консула и кастелянина», найденном в 1861 году в стене здания. Камень этот хранится ныне в фондах национального заповедника «Херсонес Таврический». Он уцелел случайно, так как во время оккупации Балаклавы в 1854-1856 гг. итальянский командующий Альфонс де Ла-Мармора вывез из все генуэзские надписи, сообщавшие о времени строительства и реконструкции башен Чембало. Надпись Симона дель Орто спасло то, что она была покрыта толстым слоем набела.

Впервые храм был заброшен в 1772 году, когда Балаклава обезлюдела. При турках церковь была действующей, так как «70 домов греческих неверных» здесь было и в то время. Переселенцы с островов Эгейского архипелага отстроили храм, отчасти его реконструировав в 1794 году. К традиционному византийскому крестово-купольному храму пристроили колоннаду тосканского ордера, характерную для русского классицизма конца XVIII века.

Накануне Крымской войны началась его вторая реконструкция, однако ее закончить не успели т. к. английские войска, занявшие Балаклаву, выгнали из города все местное население.

В 1875 году восстановленный храм осветили во имя святого покровителя моряков- Николая Чудотворца. Долгое время в храме хранились знамена упраздненного Балаклавского греческого батальона.

В годы Советской власти здесь размещался дом пионеров, потом клуб, а затем ОСОАВИАХИМ.

Восстановление храма началось в 1990 году по проекту архитектора Ю.Лосицкого. 13 июля 1990г. здесь впервые за многие годы была проведена служба. Теперь он был освящен во имя 12 Апостолов. Внутреннее убранство храма очень просто и строго – в соответствии с поздневизантийскими традициями. Но в этой простоте- подлинная красота старинного храма с такой удивительной и долгой судьбой.