Kirken er sandsynligvis opført engang i løbet af 1200-tallet og indviet til enten Skt. Morten eller Skt. Jørgen.
Den består af unggotisk kor og skib, mens tårnet er sengotisk, alt er bygget i munkesten, med munkeskifte.
Det nuværende våbenhus er fra 1878, da det afløste et ældre.
Kirken er annekskirke til Karleby,
hvilket den har været
allerede før
reformationen.
I 1650 blev den
lagt under
Falkerslev.

I 1688 blev det besluttet at kirken skulle lukkes, men først 8 år senere blev den faktisk lukket, og sognet blev delt mellem Karleby og Nørre Ørslev, men efter henvendelse til kongen blev den året efter atter åbnet, dog med den betingelse, at der de fire vintermåneder altid skulle prædikes først i Karleby kirke, og derefter skiftevis i de to andre, mens der om sommeren skulle prædikes hver søndag i alle tre kirker. Tredje søndag i fasten i 1697 begyndte man atter at holde gudstjeneste og det har man gjort siden.
Nørre Ørslev, Horreby og Karleby havde sognefællesskab indtil 1895, hvorefter præsten i Karleby kun var præst i 2 kirker, men fra 2003 kom Sønder Alslev sogn med i pastoratet.
I 1729 blev tårnet kalket rødt med hvide detaljer og skib
og kor og våbenhus hvidt med røde detaljer.
Kronen havde kaldsretten og ejede kirke indtil 1767,
da den blev solgt på auktion til præsten Jacob Borch.
Efter dennes død i 1801 var der forskellige ejere,
indtil den i 1822 blev overtaget af sognets gårdmænd,
og den 1. Januar 1915 overgik den til selveje.

Kirken er nu kalket hvid og har rødt tegltag. Den har ikke nogen sokkel, men hviler på en grov kampestenssyld, der er synlig særlig i nordsiden og ved tårnet. Kor og Skib har hjørnelisener på langsiderne. På korets sydside er der et portalfremspring, der når helt op til tagskægget. Heri er der en tilmuret præstedør, hvis øverste top kun er 154 cm over nuværende terræn. Vinduet i korets østgavl er nu tilmuret. Over rejsehøjde er der
i korgavlen et dobbelt savskifte, svarende til skibets gavl, der på begge sider af korets tag
har et 3 dobbelt savskifte. Toptinden på korets og skibets gavl er afdækket med munke-
tegl. Den nu tilmurede nordportal (kvindernes indgang) skærer gennem gesimsen, men er
borthugget forneden. Dørens tilmuring
med kampesten er udført i 1699. Over
skibets vinduer ses spor af ældre
vinduer; disse var i 1832 i hvert
fald på sydsiden erstattet af
firkantede vinduer.____

Fra tårnet har der været en rundbuet portal til skibet, som vist nok er samtidig med tårnet.
I tårnrummet er opsat en hvælving, som aldrig har været fuldført.
Allerede i 1590 var tårnet "brøstfældigt og slet
overalt, så der var fare for, at Klokken faldt ned,
hvis der ikke blev bragt Hjælp i tide".
I 1718 fortæller et nyt syn af kirken:
"Klokketårnets vestre Gavl er rent nedfalden
af Guds strænge Vejr, og den østre Gavl kan
ikke længe stå, det Gud forbyde, at der ikke
skulle komme sådan en Storm, så falder
samme Gavl ned og slår Sanghuset i stykker?.

Reparationen gav tårnet pyramidespir, men
i begyndelsen af det 19. århundrede blev
tårnets øverste stokværk og gavltrekanter
opført.