Впервые в летописи церковь Олевисте упоминается в 1267 году. Мощная башня, построенная в 1433 году, первоначально достигала высоты около 140 метров и в свое время давала основание считать церковь одним из самых высоких строений в мире. После многократных перестроек теперешняя ее высота более 120 метров, но здание и сейчас доминирует над городом. Люди, прибывающие в Таллин с моря, видят зеленоватый шпиль Олевисте за десятки километров от берега.

Из всех таллинских церквей в Олевисте наиболее ярко и четко выражена характерная черта готики — стремление ввысь. Особенно это чувствуется внутри церкви: средний неф, перекрытый звездообразными сводами, в два раза выше боковых. Он освещен окнами, что еще больше подчеркивает его высоту. Колокольня со шпилем была закончена только в 1649 году. Алтарь соединен с внутренним помещением узкими арочными пролетами, его декоративная обработка богаче основной части церкви, своды более сложного рисунка. Каменная скульптура у алтаря, кафедра и резные оконные рамы с переплетами созданы скульптором Экснером. Рисунки к алтарю и к бронзовым рельефам в псевдоготическом стиле выполнены художником Л. Майделем.

На наружной стене церкви, выходящей на ул. Пикк, находится резной каменный кенотаф — единственный образец такого украшения в нашей стране. В нише высечены восемь рельефных картин на сюжеты Нового завета. Во второй, более глубокой нише — высеченный из камня человеческий скелет с жабой на груди и со змеей вокруг черепа. По предположению, это работа знаменитого скульптора Генриха Бробендера Белденснейдера. Кенотаф с нишами воздвигнут в 1513—1514 годах.

Церковь Олевисте является ценнейшим архитектурным памятником.