Kohaliku rahvapärimuse järgi olnud juba aastal 1200 Nõval Püha Olevi kabel. Legend räägib, et merel olid paksus udus ekselnud Norra meremehed, kes lubasid, et kui nad eluga maale pääsevad, püstitavad nad tänutäheks
Jumalale pühakoja. Siis kuulnud nad kukelaulu ning selle peale kaldale sõites jõudsid nad Nõva randa. Nagu lubatud, ehitasid nad rannikule kõrgemale künkale, kohaliku mõisa tuuleveski kõrvale kabeli ja pühendasid selle
Pühale Olavile, Norra pühaks kuulutatud märterkuningale. Kuke auks, kelle kiremine nad õigesse suunda juhatas, on kiriku tornis tavapärase risti asemel hoopis kullatud kuke kuju. Vaadates 200 aastat vanu kaarte, kus praegune
metsajärv Lepaauk on veel merelaht ning arvestada pidevat maa kerkimist ja mere taganemist liiva kuhjumise tagajärjel, võib uskuda, et 1200. aastal loksus meri just kirikukünka nõlva all.
Külarahvas on pidanud praeguse kirikuhoone ehitusajaks 1636. aastat. Pärimusele toetudes peeti ka 1936. aastal suurejooneliselt kiriku 300ndat sünnipäeva. Hilisem dendrokronoloogiline analüüs määras kirikuseinas asuvate
palkide mahavõtmise aastaks 1749, nii et tegelikult võib kirik olla siiski sada aastat noorem ehk ehitatud umbes 1750ndatel aastatel. Samas ei pruugi see kogukonna mälule tuginev arvestus ka sugugi vale olla ja mingi osa praegusest kirikuhoonest pärinebki 1636. aastast, kuid on remonditud või osaliselt taastatud mingil põhjusel 18. sajandi keskel. Küllap annavad edasised uuringud kindlamat selgust.
29. juulil on meie kiriku nimipühaku – Norra kuninga Püha Olavi nimepäev. Muistne Norra kuningas Olav on kiriklikult pühitestud märtrina ja kõrgesti austatud kui Norra apostel, kes viis lõpule pika ja vaevalise Norra
ühendamise ja ristiusustamise protsessi. Kuningas Olavi kultus märtri ja apostlina kasvas ja levis väga kiiresti kogu Skandinaavias, Briti saartele. Madalamaadesse, Venemaale ja kaugemalegi. Eestis on Pühale Olavile peale
Nõva kiriku pühendatud ka Tallinna Oleviste, Vormsi ja mõlema Pakri saare kirikud.