Nimensä kirkko on saanut pyhimykseksi kanonisoidun Norjan kuningas Olav II Haraldssonin mukaan. Merenkulkijat pitivät Pyhää Olavia suojelijanaan.

Vuoden 1500 tienoilla kirkolla oli korkeutta 159 metriä, mikä teki siitä oman aikansa maailman korkeimman rakennuksen. Kirkon tornin huippukorkeuden syynä oli ilmeisesti se, että sitä käytettiin merimerkkinä, joka näkyi tunnetusta kauppakaupungista kauas merelle. Korkeuteen liittyi myös omat vaaransa: ainakin kahdeksan kertaa torniin on iskenyt salama ja koko kirkko on kolmesti palanut maan tasalle; niillä kerroilla liekkien loimotus on näkynyt Suomeen saakka.

Kronikoitsija Russowilla on Olevisten kirkon tornista jännittävää kerrottavaa: vuonna 1547 Tallinnassa vieraili akrobaatteja, jotka virittivät köyden Olevisten kirkon tornin huipusta kaupunginmuurille ja suorittivat päätähuimaavia temppuja kaupunkilaisten ällistykseksi.

Legendan mukaan...Tallinnan ylimykset päättivät eräänä kauniina päivänä rakentaa maailman korkeimman kirkon ja houkutella sen avulla kaupunkiin lisää kauppiaita. Mutta mistä löydettäisiin rakennusmestari, joka kykenisi suoriutumaan vaativasta tehtävästä? Yllättäen jostakin ilmestyi valtava ja vaitelias muukalainen, joka lupasi rakentaa kirkon, mutta hänen pyytämänsä korvaus oli kaupungille liikaa. Mies suostui tinkimään hinnasta yhdellä ehdolla – kaupunkilaisten tuli arvata hänen nimensä.

Outo mestari teki kovasti töitä eikä puhunut kenenkään kanssa. Kirkko alkoi jo olla valmis ja kaupunginisät muuttuivat päivä päivältä yhä hermostuneemmiksi. Lopulta he lähettivät vakoilijan tiedustelemaan miehen nimeä. Tämä löysikin rakennusmestarin talon, jossa vaimo parhaillaan lauloi lapselle kehtolaulua: ”Nuku, nuku lapsonen, pian on Olev taas täällä. Niin on kultaa tuomisinaan, että hätää ei maan päällä.” Nyt kaupunkilaiset tiesivät nimen! He huusivat mestarille, joka juuri kiinnitti ristiä kirkon tornin huippuun: ”Olev, Olev! Ristisi on vinossa!” Sen kuullessaan mies menetti tasapainonsa ja tippui alas maahan. Kerrotaan, että hänen suustaan hyppäsi sammakko ja kiemurteli käärme. Ennennäkemättömän korkean rakennuksen valmistaminen oli vaatinut pimeiden voimien apua. Kirkko sai kuitenkin nimensä salaperäiseltä rakennusmestariltaan.