Den ældste kirke i Allesø var oprindeligt bygget af træ, og da den gik til grunde, måtte beboerne i Allesø søge til Broby kirke i et par hundrede år. Kirken i Broby er i øvrigt en af landets ældste kirker, nemlig fra det 12. århundrede. Nogle adelige fruer i Allesø kom imidlertid i strid med jomfruerne fra Lundsgård i Broby og derfor byggede de adelige fruer Allesø kirke i årene efter 1450. Klokken i tårnet bærer årstallet 1453, så kirken er antagelig fra samme år, den skulle altså præcis være 500 år gammel. 

Klokken bærer indskriften HELP ? GOT ? VNDE - MCCCCLIII hvilket betyder ? Hjælp, Gud og Marie 1453.

Kirken er bygget af to gange, idet koret er tilbygget få år efter at den anden del af kirken blev bygget. Der har været i alt 4 altertavler, på den oprindelige så man Kristus og røverne og i fløjen St. Nikolaus og St. Jørgen. Om den altertavle fortæller den berømte biskop Jacob Madsen i sin visitatsbog. Senere blev der efter reformationen opsat en altertavle, der forestillede Kristus i Getsemane have. Denne blev kasseret ved kirkesyn i 1870 og i stedet kom en altertavle med et maleri og et krucifiks. Ved en restaurering i 1913 fik kirken sin fjerde altertavle, nemlig den der er i kirken nu, med motivet Jesus velsigner de små børn. Den er malet af malerinden Tony Müllerog den var en gave fra sognets beboere.

Der var ingen åbne begravelser i kirken, men ved den omtalte hovedrestaurering i 1913 fandt man dog nogle knogler under gulvet. I koret har bymændene i Allesø indsat en mindesten over præst i Allesø Carl Pedersen(præst 1654-1682). På stenen, hvis indskrift er latin, står der: 

Ved den højlærde herrens mand Carl Petersens død ? sognepræst i Allesø Næsbyhoved-Broby 1654-1682. Men efter at den misundelige død har bortdrevet Carl, sørger en skare venner, der er berøvet en så stor beskytter, der som de trængendes fader bragte mange gaver. Men du, ærværdige gamle, er fra dette livs sørgelige fængsel draget til den høje himmels lysende bolig. Fred med dig for evigt. 

Tegnene i stenens kanter er antagelig de 4 evangelisters kendetegn.

I den første tid var kirken i adelens eje, senere gik den over til staten, der ved en auktion i 1764 solgte den til justitsråd Lowsen og købmand P. Eilschow. I 1802 solgtes den til justitsråd Hans Jørgen Hansen og kancelliråd Søren Hillerup. De ?solgte? den hurtigt til gårdejer Jacob Mortensen fra Beldringe, der siges at have vundet den ved kortspil. Hans sønner Hans og Ole Jacobsenog deres sønner igen ejede kirken indtil 1910, hvor den gik videre til at blive selvejende under menighedsrådets styrelse. Værdien var da ca. 25.000 kr., der blev anvendt til vedligeholdelse af kirken.