Den bördiga Rekarnebygden hör till de trakter i Svealand, som tidigast kristnats. S:t Eskil bedrev flitig mission som förklarar att bygden tycks ha kristnats redan på 1000-talet.
Ett fragment av en kalkstenkista från mitten av 1000-talet av den typ som nämns i beskrivningen av Sundby kyrka påträffades i Kjula och detta får anses vara bevis för att en träkyrka, troligen av stavkyrkotyp, fanns här.
På 1100-talet har den ersatts med en romansk kyrka av gråsten. Av den har långhusets murar och tornet bevarats. 1798 gjordes en genomgripande ombyggnad. Kyrkans inre präglas av denna.
Kyrkan rymmer 220 personer.