La chiesa di San Paolo sorge su una modesta altura, cuore religioso e acropoli dell’abitato antico e moderno. Le indagini archeologiche attestano la presenza di un santuario, esistente probabilmente già nelle prime fasi, fenicia e greca, di vita della città, e nelle successive epoche punica e romana. La divinità venerata era la più importante di Olbia antica: il dio fenicio e punico Melqart, ovvero l’Eracle dei Greci e l’Ercole dei Romani. La testa della statua fittile di Ercole esposta al Museo Archeologico è una copia, realizzata in età romana, della statua del culto del santuario.
La chiesa attuale, risalente nella sua forma originaria al XVIII secolo, si caratterizza per la cupola sormontata da lanterne rivestita esternamente da piastrelle di ceramica colorata.
