Kao i ostale župne crkve otoka Ugljana tako je i crkva sv. Pavla u Kukljici sljednica srednjovjekovne građevine koja je obnovljena g. 1666. u skromnom baroknom slogu. Neke župne crkve građene su još za vrijeme ranoga kršćanstva. Prvi spomen imena Kukljice je iz g. 1106. (darovnica maslinika u Kukljici samostanu sv. Krševana u Zadru) i glagoljske župe g. 1405., za koju se pretpostavlja da je ustanovljena i prije.
Starija župna crkva, za koju nema podataka o izgledu, spominje se u dokumentima iz g. 1589. i 1603. Župnik Petar Šulić, bratovština, župljani i graditelj Matija Senestrina ubilježeni su na glagoljskom natpisu arhitrava iznad glavnoga ulaza, koji je bio postavljen u obnovi crkve g. 1666. Crkvu je posvetio zadarski nadbiskup Ivan Parzego 11. siječnja 1673. (ploča na sjevernom zidu prezbiterija). Sve ugljanske župne crkve (osim one u Ugljanu) četvrtastoga su tlocrta s isto takvom apsidom, koja služi za sakristiju.
Kukljička župna crkva (16 x 9 m) ima odijeljen zvonik, izgrađen sa sjeverne strane sakristije g. 1744. Takav tip zvonika bio je prototip za zvonike u Sutomišćici (1836.), Preku (1844.) i Kalima (1892.).
Crkva je smještena u središtu mjesta i opasana je zidom. Dio staroga groblja, koje je uklonjeno u 18. st., vidljiv je u nekoliko nadgrobnih ploča na jugoistočnom dijelu. Građena je od klesanoga kamena od domaćih klesara koji su radili po cijelom otoku i šire. Pročelje je s jednostavnom baroknom profilacijom ulaza s postoljem biljnih ukrasa, dva bočna prozorčića i četverolisnom rozetom.
Nekada je ispod rozete bio reljef sv. Pavla. Na vrhu pročelja nalazi se kameni kip Krista koji blagoslivlja. Na bočnim zidovima postavljeni su polukružni prozori, danas ispunjeni vitrajima, a isti se prozor nalazi i na začelnom zidu apside. Bočni je ulaz izveden na južnom zidu. Mise su nedjeljom u 9.30 i srijedom u 18 sati.
