Det er dog nærliggende at antage, at kirken og sognet er opkaldt efter den Marie Magdalene, der var med i Jesu følge, og som kom og fandt hans grav tom påskemorgen.
Den nuværende kirke er opført omkring 1450 af Otto Nielsen Rosenkrantz til Høgholm og hans hustru Else Holgersdatter Krognos. Våbenhuset er fra omkring 1500, og kirken blev berømt i indland og udland på grund af de to høje og kraftige flyverønnetræer, der gennem et par hundrede år voksede over våbenhusdøren. De gik ud omkring 1980, og nu er der frit udsyn til det gamle solur over døren. Tårnet kom til i 1595. Kapellet midt syd blev opført i 1639.
Kirken har kalkmalerier, munkestensalter, orgel og 180 siddepladser.
Cykelvenlige vejkirker: her kan cyklen parkeres, du kan få fyldt din vandflaske, og der er en cykelpumpe til rådighed.