Bei der Grundsteinlegung für den Bau der Maria-Magdalenen-Kirche am 10. Juni 1900 wurde unter anderem folgende Urkunde eingemauert, die Auskunft über die Baugeschichte der Kirche gibt. Abgedruckt wurde sie einen Tag später in der Bergedorfer Zeitung.
„Im Namen Gottes des Vaters und des Sohnes und des heiligen Geistes! Was Gott sich vorgenommen und was er haben will, das muß doch endlich kommen zu seinem Zweck und Ziel!
Am 1. Oktober 1894 ist Reinbek zusammen mit den Ortschaften Schönningstedt, Ohe und Glinde selbstständige Kirchengemeinde geworden. Seit 25 Jahren hat man in Reinbek ein Gotteshaus bauen wollen. Nun solls That und Wahrheit werden. Dem Herrn sei Dank! Bei der großen Ausdehnung der Kirchengemeinde Steinbek – sie erstreckte sich von Hamburg bis Reinbek – war eine genügende kirchliche Versorgung und mehr noch eine seelsorgerische Wirksamkeit unter der starken Zunahme der Seelenzahl zur Unmöglichkeit geworden. Sie mußte sich im Wesentlichen darauf beschränken, daß der Pastor aus Steinbek allmonatlich einmal in der Reinbeker Schloßkapelle Gottesdienst abhielt und Amtshandlungen vollzog. Immerhin hatte Reinbek an der alten Schloßkapelle einen Raum, der nur dem Gottesdienst geweiht war. Als es nun im Jahre 1875 fraglich wurde, ob dieser Raum weiterhin für die Gottesdienste zur Verfügung stehen würde, faßte man den Plan, in Reinbek eine Kapelle zu bauen, die von Steinbek aus pfarramtlich versorgt werden sollte. Es bildete sich ein Komitee aus Reinbeker Herren, welche unter dem Vorsitz des Steinbeker Pastors eine ganze Reihe von Verhandlungen über den Kapellenbau pflog. Wegen mancherlei äußerer Schwierigkeiten mußten diese Verhandlungen jedoch nach einiger Zeit wieder abgebrochen werden, ohne zu irgendeinem Ziel geführt zu haben. Und da es sich herausstellte, daß die Schloßkapelle auch fernerhin für die Gottesdienste würde benutzt werden können, schlief die Kapellenbau-Frage ganz wieder ein und zwar für eine ganze Reihe von Jahren.
Am 10. April 1891 trat der nun schon seit einem Jahre in die Wohnungen des ewigen Friedens abgerufene Ruperti in das Amt eines General-Superintendenten und Bischofs für Holstein. Das war für Holstein sehr bedeutungsvoll, denn mit diesem Manne kam es wie ein Frühlingswehen über die holsteinische Landeskirche. Vornehmlich ihm und seinem warmen Wirken für die Theilung der großen Gemeinden ist es zu danken, daß unter Gottes Segen während seiner achtjährigen Wirksamkeit in Holstein 20 neue Kirchen eingeweiht werden konnten. Dank seiner Bemühungen bekam auch Reinbek im Mai 1892 zunächst einen eigenen Pastor, dem als Hülfsgeistlichen der Kirchgemeinde Steinbek die Ortschaften Reinbek, Schönningstedt und Ohe als Amtsbezirk überwiesen wurden. Alsbald erwachte auch wieder das Interesse für den Kirchenbau und wurde durch den Pastor neu belebt mit um so besserem Erfolg, als sich von da ab der enge Raum der alten Schloßkapelle je länger je mehr als unzureichend erwies. So wurden denn in kurzer Zeit durch eine Hauskollekte rund 12000 M an freiwilligen Gaben für den Kirchenbau zusammengebracht.
Als nun am 1. Oktober 1894 Reinbek mit den Ortschaften Schönningstedt und Ohe unter Hinzuziehung von Glinde selbstständige Kirchengemeinde wurde, hätte man alsbald der Kirchenbaufrage praktisch näher treten können, wenn nicht das Konsistorium in Kiel es angestrebt hätte, auch das bisher zur Kirchengemeinde Hohenhorn gehörige Dorf Wentorf mit bei Reinbek einzupfarren. Am 1. April 1898 kam die Entscheidung. Seitdem gehört Wentorf zur Kirchengemeinde Reinbek.
Es war nicht leicht für unsere Kirche, den rechten Bauplatz zu finden. Lange gingen die diesbezüglichen Wünsche und Meinungen weit auseinander. Schließlich wurde aber am 6. Juli 1899 zu unserer Aller Freude dieser Platz fast einstimmig gewählt und am 20. April 1900 endgültig gekauft.
Der allgemeine Bauplan für die Kirche wurde am 28. November 1898 vom Kirchenvorstand und Kollegium festgestellt. Am 23. März 1899 wurde der Architekt Herr. H. Groothoff in Hamburg endgültig mit der Ausarbeitung des Projekts und Kostenanschlages beauftragt. Nachdem das fertiggestellte Projekt vom Kirchenvorstand und Kollegium angenommen und am 1. März 1900 von den Behörden genehmigt worden war, wurde die Ausführung des Baues am 26. April 1900 unter 9 Bewerbern aus der Gemeinde dem Maurermeister Carl Ohl übertragen. Am 30. April 1900 wurde der erste Spatenstich für den Kirchenbau gethan.
Eine rechte Zierde des Bauhandwerkes soll unsere Kirche nun mit Gottes Hülfe emporwachsen zu einem weithin sichtbaren Denkmal, das mit seinem Thurm nach oben weist, mit ausgerecktem Finger.
Gott segne und schütze alle, die daran arbeiten! Heute, da wir nun die Feier der Grundsteinlegung begehen, stehen wir hier mit Dank gegen Gott, der bisher geholfen, und mit dem Gebet, daß Er, der treue Gott und Heiland, das begonnene Werk auch weiterhin fördere, segne und zum Ziel führen werde, auf daß an dieser Stelle erstehe ein freundliches Gotteshaus, eine Stätte des Friedens und der stillen Einkehr, in der allzeit das Wort Gottes lauter und rein verkündet werde und die heiligen Sakramente recht verwerthet werden zur Ehre Gottes und zum Segen unserer Gemeinde.
Das walte Gott!
Reinbek, am Trinitatisfest, den 10. Juni 1900
Der Kirchenvorstand
Pastor A. Fries
Kiehn, Amtsvorsteher
Hugo Duttenhofer, Amtsgerichtsrath
Behn, Gemeindevorsteher
Hintze, Mühlenbesitzer
August Mann, Kaufmann“
Ferner wurden in den Grundstein eingemauert eine Bibel, ein Gesangbuch, ein Katechismus, mit passenden Inschriften versehen, der Bauplan, Münzen, Photographien, Exemplare der Bergedorfer Zeitung, in denen sich die auf den Bau bezüglichen Anzeigen befinden, und Anderes mehr.
