I 1979 grunnla Stein Olsen bandet Nordnorsk Rockensemble, som i 1981 skiftet navn til Karlsøy Prestegaard. De gav ut sin første 7"-singel i 1981. Året etter spilte bandet inn debutalbumet Dyret (666). De hadde en pause fra 1986, men gjenoppstod i 1988.[1]
I 1994 komponerte bandet musikken til Svein Andersens dokumentarfilm Karlsøya – mellom geiter, rock og Muhammed.[3] En soundtrack-CD på eget selskap ble også lansert i anledning filmen.[4] Både gruppa og Stein Olsen som privatperson medvirket i filmen.
Den 13. juni 2008 ble albumet Dyret (666) og singelen «Barn av lyset» reutgitt som CD av Smart Patrol Records.[1]
Bandet var i 2023 fortsatt aktivt konserterende og turnerende, hovedsakelig i Nord-Norge, der de blant annet er fast deltaker (og arrangør) på den lokale Karlsøyfestivalen. I 2004 spilte de på Quartfestivalen, som omtalte dem som «midt i blinken, vi snakker attitude og rockehistorie så det holder».[5]