Herritslev Kirke er en af de mange rødkalkede kirker på Falster og Østlolland. Den er opført ca. 1220 på Valdemar Sejrs tid bygget af store røde munkesten i romansk stil. Bygningen var fra starten uden tårn og hvælvinger som blev tilføjet 150-200 år senere i gotisk stil. Tårnet har pyramideformet spir.
Kirkens hovedindgang er nu gennem tårnet i kirkens vestende, men der har været flere andre indgange. Indtil en brand i 1608, og måske senere, har der været et våbenhus på sydsiden, og der har også været en nu tilmuret portal på nordsiden. Den var i brug frem til 1867.
Inventar m.m
Altertavlen er en gipsafstøbning af C. V. Bissens relief: Christus og Disciplene i Emmaus.
Prædikestolen er snedkret i hollandsk højrenæssance ca. 1610. På den er fremstillet de fire Evangelister.
Kirkens orgel er et Starup-orgel fra 1966, oprindelig med fire manual-stemmer. Men i 2000 blev det udbygget med subbas og pedal.
I koret er indmuret en ligsten over præsten Zacharias Christoffersen 1639 og 2 hustruer.
og en over 2 af børn af en tidligere præst
I kirken blev 1920 afdækket en del kalkmalerier fra ca. 1250 og ca. 1300. De er imidlertid i ret dårlig stand og delvis tildækket igen.
Kirkegård
Til kirken hører 2 kirkegårde, en nyere på den anden side af landevejen. og omkring kirken den gamle kirkegård, som er bemærkelsesværdig ved at have bevaret det oprindelige middelalderlige stendige.
Omskifteligt tilhørsforhold
Herritslev kirke var til 1695 hovedkirken i et pastorat, hvortil Bregninge Sogn var anneks. Men nævnte år annekteredes Herritslev til Nysted Sogn og Bregninge til Kettinge Sogn. I 1906 blev Herritslev atter selvstændigt pastorat. Indtil 1. april 1920 var sognepræsten dog desuden residerende kapellan for Nysted Købstad. I 1964 blev Herritslev sammenlagt med Døllefjelde–Musse pastorat.