La chiesa di San Paolo è situata ai piedi del colle San Giovanni, lungo una strada che conduce dalla Porta Nord verso la Porta Sud – quella che nel passato effettivamente era la strada maestra della città di Cattaro. Situata dietro le apsidi della Cattedrale, la chiesa di San Paolo era completamente nascosta dietro un muro alto in modo tale che unicamente un portale in stile romanico-gotico faceva intuire che da lì esisteva un complesso architettonico significativo.
La chiesa di San Paolo fu costruita come donazione da un cittadino di Cattaro di nome Paolo Bari nel 1263. Di questo fatto ne testimonia la scritta sulla facciata che fa riferimento al re di Serbia Uroš I, il papa Urbano IV e il vescovo di Cattaro Marco.
Accanto alla chiesa esisteva dapprima un convento maschile, e dal Cinquecento anche quel femminile domenicano. Dentro quelle mura finì la sua vita nel 1565 rinchiusa in una cella la santa martire di Cattaro, chiamata Beata Osanna. Qualche anno prima, ovvero nel luglio del 1539, Ariadeno Barbarossa, malfamato ammiraglio e comandante della flotta ottomana, si era avviato verso Cattaro. Gli ottomani hanno attaccato la Porta del Nord, però furono riscontrati da numerose cannonate. Al culmine della battaglia, la domenicana Osanna uscì dal suo convento e si presentò nella parte Nord delle fortificazioni. Con la sua apparenza furono recuperate le forze e la confidenza necessarie, dopodiché Barbarossa fu costretto a ordinare il ritiro e l’allontanamento dalle Bocche di Cattaro. Così quella minuta domenicana cattarena Osanna combatté il pirata crudele e salvò la sua città da una sorte fatale.
Quando la chiesa fu occupata dalle armate di Napoleone (1807-1814) e trasformata in caserma, il suo interno era diviso in due livelli tramite una costruzione che univa i suoi piani. In quel modo fu perso quel concetto di uno spazio unico tipico per le chiese. Durante l’occupazione italiana nella Seconda Guerra mondiale invece fu adattata in una prigione, e nei tempi del Cominform e degli scontri tra Tito e Stalin nel 1948, nella chiesa fu aperta la prigione femminile, la cosiddetta Piccola Prigione.
Durante i lavori di ricerche eseguiti nella chiesa, sono state fatte delle analisi che hanno rivelato che la costruzione odierna era stata allargata nel Cinquecento, mentre dalla chiesa originaria del Duecento sono stati conservati una parte della facciata principale occidentale con il portale e l’incisione sulla costruzione ed una volta absidale senza abside nei muri laterali della nuova chiesa. Le fondamenta dei muri laterali della chiesa antica ed i resti del pavimento di pietra in forma della scacchiera diagonale sono stati scoperti durante i lavori di escavazione e presentati all’interno della chiesa stessa.
I lavori di escavazione sono stati eseguiti in un cortile stretto situato tra il muro occidentale della chiesa ed il muro alto verso la strada. Questi scavi hanno fatto rilevare che nel Duecento si entrava nella chiesa da un livello inferiore rispetto a quello presente tramite una scala a due ali. Sotto questa scala è stato costruito un arcosolio, nella cui nicchia è stato eretto un sarcofago in pietra e che potrebbe ben essere la tomba del patrono dell’antica chiesa.
Questo prezioso spazio è stato restaurato e adattato in uno spazio museale allestito per le mostre dove è adesso esposta una ricca collezione dei monumenti in pietra appartenenti al Lapidario della città, ma che può anche essere usato come una sala polivalente sia per le mostre, che per concerti, convegni, ed altro.