L'aspetto generale dell'edificio è di forma cubica, realizzato con un particolare intreccio di grossi mattoni uniti tra loro dalla malta. L'antico tempio è diviso in tre navate, o nove quadrati uguali da quattro colonne di spoglio, provenienti con molta probabilità da monumenti archeologici dell'antica Kaulonia. Nel fusto di una di esse si legge l'iscrizione in greco referente al mistero dell'Epifania "Dio il Signore apparve a noi". Un'altra colonna poggia su un capitello corinzio rovesciato. Questo particolare potrebbe significare che il tempietto in origine era di culto cristiano.
Le tre absidi orientate costituivano l'elemento centrale della liturgia bizantina. La centrale è detta bema, e conteneva un piccolo altare; quelle laterali avevano funzione di prothesis a sinistra e diaconikon, a destra. Sulla parte di ponente la costruzione si adagia per lo più sulla roccia nuda, mentre la parte di levante, che termina con tre absidi, poggia il suo peso su tre basi di pietra e di materiale laterizio.

La Cattolica esternamente è quasi priva di decorazioni, a parte le cupolette che ne sono ricche, rivestite di mattonelle quadrate di cotto disposte a losanga, e di due cornici di mattoni disposti a dente di sega lungo l'andamento delle finestre.

La particolare collocazione delle fonti di luce all'interno della Cattolica, mette in risalto lo spazio e conferisce maggiore slancio. Questa dilatazione dello spazio serviva a mettere in risalto gli affreschi di cui i muri della chiesa erano interamente ricoperti in origine, decorazioni pittoriche dunque a cui era affidato il compito di decontestualizzare la superficie muraria. Sulle pareti si notano affreschi a più strati, che testimonierebbero il passaggio attraverso cinque cicli di storia.

Il primo strato è relativo al X secolo (raffigurazioni di santi guerrieri), stile bizantino; il secondo strato pittorico è di epoca normanna (San Giovanni Crisostomo, basiliano); il terzo è di epoca sveva (Annunciazione); il quarto di tecnica gotica-internazionale (San Giovanni Battista e altri santi); l'ultimo rappresenta "il sonno eterno della Vergine", sul manto della Madonna si notano gigli angioini.

La Cattolica era la chiesa madre tra le cinque parrocchie del paese, retta da un vicario perpetuo (succeduto al protopapa di epoca bizantina), che aveva diritto di sepoltura al suo interno. ne sono testimonianza i resti umani rinvenuti in un sepolcro marmoreo con un anello di valore.

La denominazione di Cattolica stava ad indicarne la categoria delle "chiese privilegiate" di primo grado, infatti con la nomenclatura impiegata sotto il dominio bizantino nelle provincie dell'Italia meridionale (soggette al rito greco), la definizione di katholikì spettava solo alle chiese munite di battistero. Cosa che è rimasta fino ad oggi in certe località legate per tradizione a questo titolo, come ad esempio la chiesa "Cattolica dei Greci" di Reggio Calabria che fu la prima della città. In effetti l'architettura, la ricchezza degli affreschi e la copertura in piombo delle cupole dimostrano che non si tratta di un tempietto di minore importanza. La Cattolica di Stilo, costituisce un'architettura puramente e tipicamente bizantina, come si può vedere dalla pianta e dalla costruzione, unico esempio del genere con la sua gemella di San Marco in Rossano.

Il piccolo ambiente della chiesa è munito di tre absidi sul versante orientale: quella centrale (il bema) conteneva l'altare vero e proprio, quella a nord (il prothesis) accoglieva il rito preparatorio del pane e del vino, mentre quella a sud (il diakonikon) custodiva gli arredi sacri e serviva per la vestizione dei sacerdoti prima della liturgia.