U središtu bizantske utvrde sv. Kuzme i Damjana na brdu sv. Damjana iznad Barbata u 6. st. izgrađen je ranobizantski sakralni objekt koji je često bio pregrađivan, a nastupom mira nakon završetka Gotskoga rata (535. – 554.) i zapostavljen.
Crkva, koja je također posvećena sv. Kuzmi i Damjanu, jednobrodna je građevina s prostranom polukružnom apsidom i srušenim pročeljem koje je okrenuto prema glavnomu zapadnomu ulazu u utvrdu. Smatra se da je apsida imala polukalotni svod (polukupola kružnoga presjeka), a iznad četvrtastoga je broda bilo drveno krovište. Lađa crkve pregrađena je u dva traveja (polje na svodu s uzdužnim ili poprječnim lukovima) s plitkim pilastrima (vertikalne istake na zidu). Najočuvaniji su dijelovi vanjskoga zida svetišta s pet plitkih niša i četiri lezene (izbočeni polustupovi) spojene lukovima. Na sredini apside je bifora (dvokrilan prozor razdijeljen stupićem) s lukovima, koja je kasnije zazidana sedrom.
U XII. i XIII. st. izvršene su pregradnje dodavanjem pojasnice između dvaju križnih svodova i novih zidova uz postojeće čeone zidove trijumfalnoga luka crkve te je ona bila smanjena s obzirom na prvotnu veličinu. Radovi su izvršeni dosta površno jer je prestala ratna opasnost te se sve uglavnom urušilo do sredine XIX. st.
Tlocrt utvrde je nepravilan trokut, a dimenzije i površina fortifikacije od 4,2 ha upućuju na jedan od najvećih obrambenih zdanja bizantske vladavine u Dalmaciji. Slične utvrde bile su podignute na poluotoku Kaštelinu u Kamporu (mozaik su devastirali turisti) i na Punti Zidine u Loparu iz istoga vremena. Tamo se vrše ili su izostala arheološka istraživanja. Od susjednih otoka Bizant je izgradio dvije slične utvrde na Krku i jednu na Pagu.
