Kościół zbudowany został w XIII wieku. W 1306 roku został poświęcony przez biskupa Utrechtu. Był rozbudowywany do połowy XVI wieku, kiedy to uzyskał swój ostateczny wygląd. W 1566 roku otrzymał ośmiokątną dzwonnicę; w 1658 roku zawieszono w niej carillon, składający się z 47 dzwonów, odlany w pracowni Francois Hemony. W 1724 roku dodano organy, uchodzące dziś za najlepsze w całej Holandii[1]. Kościół ma powierzchnię 3300 m².

Do roku 1865 w kościele grzebano zmarłych. Znajduje się tu 2500 grobów, w których pochowano 10 000 mieszkańców Amsterdamu. Wśród nich znajdują się osobistości, które zapisały się w historii Holandii: Jacob van Heemskerck, Cornelis de Graeff – burmistrz Amsterdamu, Kiliaen van Rensselaer, jeden z założycieli Nowego Amsterdamu na Manhattanie, dzisiaj znanego jako Nowy Jork. W kościele ostatnie miejsce spoczynku znalazł również znany kompozytor Jan Pieterszoon Sweelinck, wieloletni organista Oude Kerk (od 1577 lub 1580 do 1621 roku).

Przed przejściem na protestantyzm, które dokonało się w roku 1578, Oude Kerk był kościołem katolickim. Wewnątrz widoczne są jeszcze ślady po dawnych dekoracjach. W tym samym roku Oude Kerk zaczął również pełnić rolę biura matrymonialnego. Używany był także do przechowywania miejskich archiwów.

Rembrandt często uczęszczał do Oude Kerk, a jego dzieci tutaj zostały ochrzczone. Żoona Rembrandta Saskia van Uylenburgh została tu pochowana w roku 1642. Jest to jedyny budynek w Amsterdamie, który zachował swój oryginalny wygląd od czasów Rembrandta.