Cо времен генуэзского владычества в Балаклаве сохранилась церковь - сейчас храм Двенадцати апостолов (ул. Рубцова, 41). По одной из версий, она была построена в 1357 году, о чём гласит надпись на камне, обнаруженном под слоем штукатурки во время реставрации: «1357, в день сентября, начата эта постройка во время управления скромного мужа Симоно-де-Орто, консула и кастеляна».
В 1794 году церковь была отреставрирована, также появился портик. Неизвестно, в чью честь был освящен храм изначально; по окончании Крымской войны церковь освятили в честь святого Николая.
В советские времена в церкви был устроен дом пионеров, а затем клуб Осоавиахим. После передачи храма в 1990 году Церкви он был переосвящен в честь Двенадцати апостолов.