Ejlby kirke er en romansk middelalderkirke, bygget ca. år 1200.
Kirken var oprindeligt viet til Sankt Ursula, der ifølge legenden var en kristen prinsesse, som tog på pilgrimsfærd gennem Europa inden sit giftermål. I Køln blev hun og de 11.000 jomfruer, der rejste med hende, dræbt af hunnerne. Hun var en meget populær helgen i middelalderen. Efter reformationen 1536 forsvandt billederne af hende og hendes jomfruer fra kirken.
Kirken er blevet bygget om flere gange, bl.a. tårnet der engang havde bindingsværksoverdel med fire gavle. Tårnet faldt ned i 1600-tallet, bl.a. efter Svenskekrigene i 1657-1660, hvor svenske soldater og lejetropper plyndrede og hærgede Fyn, også de fynske kirker. Derfor blev der renoveret og bygget en del til, da de igen var væk. Ved kirkens nordlige side er der en portal med køreport og låge, der er fra omkring 1500-tallet.
Kirken blev senest efter Reformationen overtaget af Kronen, men fra 1607 blev ansvaret - og de penge, bønderne betalte til kirken - overtaget af adelsmanden Frederik Quitzow til Sandagergård, og siden har kirken både hørt under Quitzow-familien og Rugård, inden den fra 1687 kom under herregården Jerstrup og fra 1804 under grevskabet Gyldensteen, der overtog Jerstrup. I 1912 overgik kirken til selveje.