Den nuværende kirke er grundlagt af ægteparret rigshofmesterenOtte Nielsen Rosenkrantz og Else Holgersdatter Krognos, der ligeledes stod bag opførelsen af kirkerne i Tirstrup og Bregnet. Opførelsen er sket engang i perioden 1425-58. Til de oprindelige dele hører skibet og koret med apsis. Bygningen er opført af munkesten på en sokkel af granitkvadre fra en ældre kirke. Byggeriet skete på et sted, hvor ”Skov og træer stode, og de havde ladet bortrydde”. I korhvælvingen og apsis er 1904 fundet og afdækket kalkmalerier, der viser grundlæggerparrets våbenskjolde, samt våben for aarhus-bispenUlrik Stygge (1423-49). Hvælvingerne i skibet er dog indbygget ca. 1500 af sønnesønnen Niels Eriksen Rosenkrantz og hustru Birgitte Olufsdatter Thott. Deres våben og navne er malede på skibets østlige hvælving sammen med en dommedagsscene.
Tårnet er opført 1593 af Mogens Juel til Ryomgaard. Tårnet havde indtil 1739 et spåndækket kuppelspir, i dag et almindeligt saddeltag. Det store sydvendte hvælvede gravkapel er vistnok opført 1639. På kapellets gavl ses årstallet 1780 og initialerne ”HG”, antagelig for ægteparret Palle Krag Hoff og Anne Marie Galthen på Ryomgaard. Dette referer uden tvivl til en restaurering. Våbenhuset er ligeledes fra en senere tid.
Tirstrup Kirkes tilknytning til herregården Gl. Ryomgård afspejler sig også ved de gravminder, ligsten og epitafier, som ses i kirken.
I kapellet findes et epitafium over etatsrådPeder Fogh (†1753). Han var en søstersøn til Peder Griffenfeldt og blev adlet 1707. Epitafiet er tillige et minde om hans tre hustruer, som han roser i lange blomstrende latinske indskrifter. Et udskåret gitter ind mod koret bærer ligeledes hans våben. Under kapellet findes tillige en gravhvælving.
I mange år var Marie Magdalene Kirke kendt vidt omkring, da der midt på gavlen af kirkens våbenhus voksede to flyverøn. Megen overtro var forbundet med disse træer. I 1980 døde dog det sidste af de to træer.
Kilde
Trap Danmark – fjerde udgave, 6. bind, Randers Amt