Prinsesse Sunnivas historie er først beskrevet i sagaen om Olav Tryggvason fra 1100-tallet, og noen år senere i et skrift av den islandske munken Gunnlaug. De mange underlige hendelser som fant sted på Selja, har til alle tider fascinert både religiøse og verdslige forfattere, deriblant Sigrid Undset. Prinsesse Sunniva var datter av en irsk småkonge. Hun ble strengt oppfostret i den kristne tro i et kloster, og hun ble beundret for sin klokskap og godhet. Da hennes far døde, arvet hun riket og styrte mildt og kjærlig sine undersåtter. Så fridde en mektig vikingkonge til henne, men Sunniva ville ikke ekte en hedensk mann. Han truet da med å herje i hennes land for å få hennes samtykke. Men Sunniva var bundet av sitt løfte til Gud og kune ikke gifte seg. Hun frigjorde derfor sine undersåtter fra sine plikter og sa at de som ville, kunne følge henne eller bli. Hun var så høyt elsket i sitt land at en stor skare av kvinner og menn ville reise med henne. Tre store båter ble utstyrt for flukten. Våpenløse gikk de ombord og lot båtene drive ut mot havet. "Jeg overlater vår skjebne til Gud og ber ham styre vår ferd" sa Sunniva ved avreisen.

De drev til sist mot norskekysten hvor de ble møtt av nordmenn som kastet stein og skjøt på dem med pil og bue. Irlenderne drev utover igjen og endte opp i en fryktelig storm som skilte båtene fra hverandre. En forsvant, og de to andre strandet på øya Selja. Her fant de en hule i fjellet hvor de kunne skjule seg. Folk på fastlandet brukte øya til beite for sauene sine. Noen av dyra forsvant, og skylden ble lagt på de fremmede som ble oppdaget av noen gjetere. Håkon Jarl ble budsendt og kom med væpnede menn for å ta de fremmede røverne til fange. Irlenderne så dem komme og ante hva som skulle skje, men var ikke redde og foretrakk døden fremfor å falle i hedningenes hender. Sunniva samlet folket i hulen, og der ba de Gud om å gi dem en verdig død. En stor helle falt da ned over dem, og et seinras skjulte åpningen til hulen. Alle døde, og da Håkon Jarl kom frem, fant han ingen fremmede der.

En tid senere seilte høvdingene Tord Jorunnsson og Tord Egeleivsson forbi øya. De fikk se et vakkert gyldent lys stråle over øya. Undrende gikk de i land for å undersøke, og de fant et menneskehode på det sted hvor lyset skinte. De tok hodet med seg til Olav Tryggvason. "Dette må være hodet til en hellig mann" sa han. Men det var flere underlige hendelser på øya. En bonde lette etter hesten sin og fikk øye på den like nedenfor Sunnivahulen. Han gikk dit og fikk se et stort lys på stedet. Da kongen og biskop Sigurd fikk høre om dette, reiste de straks for å undersøke. De fant inngangen til hulen og fjernet stinene. En masse søtduftende menneskeben kom til syne, og innerst i hulen lå den vakre Sunniva med sitt lange skinnende hår og sin fine hud, hel og uskadd som om hun sov. Den kristne kong Olav Tryggvason forstod straks at hun måtte være en sann helgen. Han bestemte seg for å bygge et kapell i hulen og en kirke utenfor. Dette ble den første norske kirke, og Sunniva ble regnet for den første norske helgen. Den hellige Sunniva ble lagt i en kiste som først stod i kirken oppe i fjellet, og i 1170 ble kisten flyttet til domkirken i Bergen. "Seljemannamesse" er minnefesten for Sankta Sunniva og hennes følge og feires 8. Juli.