Auf der Grundlage schriftlicher Überlieferung ist die Geschichte von Cölln ab dem Spätmittelalter relativ gut nachvollziehbar. Zur hochmittelalterlichen Geschichte der Siedlung und zur Stadtgründung sind die Nachrichten aber noch spärlich. Aus Mangel an Quellen und weil man von einer Parallelentwicklung beider Städte ausgeht, werden bei der wissenschaftlichen Betrachtung
der Frühgeschichte der Doppelstadt Berlin/Cölln oft Urkunden hinzugezogen, die sich nur auf eine der beiden Städte beziehen.

So auch im Fall der Altersbestimmung von Berlin. Die älteste überhaupt vorhandene Urkunde stammt aus dem Jahr 1237. In dem Schriftstück geht es um einen Vergleich in einem Streit zwischen den Markgrafen und dem Bischof von Brandenburg um die Erhebung des Kirchenzehnts. Am 28. Oktober 1237 unterzeichnete Symeon, Pfarrer von Cölln (Symeon plebanus de Colonia), als Zeuge die Urkunde, in der der Streit begelegt wird.

Diese Urkunde enthält die früheste schriftliche Erwähnung des Berliner Raumes und wurde zur Grundlage der 700- und zuletzt der 750-Jahrfeier Berlins im Jahr 1987. Symeon, erscheint hier als Geistlicher, der eine Pfarrei, das heißt eine Kirche mit einem räumlich abgegrenzten Einzugsbereich
verwaltete. Die einzige Pfarrkirche der Stadtgemeinde Cölln ist stets die Petrikirche. Derselbe Geistliche tritt am 26. Januar 1244 in einer zweiten Urkunde hervor, diesmal jedoch als Propst von Berlin (dominus Symeon de Berlin prepositus). Drei Jahre später, am 29. April 1247, wird Symeon in einer Urkunde als Propst von Cölln bei Berlin bezeichnet (Symeon prepositus de Colonia juxta Berlin).

Aus den scheinbar verwirrenden, unterschiedlichen Benennungen Symeons ergibt sich eine Rangsteigerung. Als Propst ist Symeon nicht nur einfacher Pfarrer, sondern zugleich der Vorgesetzte weiterer Pfarrer. Es muss auch davon ausgegangen werden, dass Cölln und Berlin zu dieser Zeit einen gemeinsamen Propsteibezirk bilden. Dieser wird später wieder getrennt.
Die bekannten Urkunden belegen eine erneute Vereinigung der Berliner und der Cöllner Propsteien erst im Jahr 1319.

Aus den erhaltenen Urkunden geht jedoch hervor, dass Cölln und Berlin zumindest in der kirchlichen Verwaltung eine zentralörtliche Funktion hatten, denn einem Propst waren in der Regel die Pfarrer benachbarter Gemeinden untergeordnet.

Zudem belegen die Urkunden die Existenz von Kirchbauten in beiden Städten. Das Amt, das Symeon als der älteste namentlich bekannte Berliner inne hatte, gibt es auch heute noch: das des Pfarrers der Petrikirchgemeinde. Er trägt heute das Propstkreuz. Die Gemeinde als älteste noch existierende Kirchengemeinde der Stadt wurde mit der Luisenstädtischen-, der Parochial- und der
Marienkirchgemeinde vereinigt. Ihr Gotteshaus ist heute die Marienkirche am Alexanderplatz.

Die Anfänge
Andacht auf dem Petriplatz zu Ehren der Toten

Trotz des Verlustes ihrer Kirche verstehen sich die Mitglieder der Petrikirchgemeinde als aktive und geschichtsbewusste Berliner Christen, die großen Anteil an den jetzigen Bergungsarbeiten auf dem Friedhof und an den Freilegungen der Kirchenfundamente nehmen.

Bevor die Gräber auf dem Kirchhof ausgegraben wurden, hat die Petrikirchgemeinde gemeinsam mit dem Grabungsteam eine Andacht zur Erinnerung an die Toten abgehalten.

Der Plan von Johan Gregor Memhardt aus dem Jahr 1652 zeigt 32 bedeutende Baulichkeiten in Berlin und Cölln. In diesem Plan sind deutlich die Grundzüge einer mittelalterlichen Stadtanlage kurz vor dem Wandel zu einer Festungsstadt zu erkennen.

Stadtgründungsurkunden sind weder für Cölln noch für Berlin überliefert. Die schriftlichen Zeugnisse, in denen Symeon Erwähnung findet, zeigen aber an, dass zu dieser Zeit, 1237 und
1244, eine feste kirchliche Organisation des Berliner Raumes bestand, die schwerlich erst unmittelbar vor der Urkundenniederschrift entstanden war. Die Doppelstadt muss wesentlich früher
entstanden sein.
Bei allen Plänen, die das mittelalterliche Cölln und Berlin zeigen, handelt es sich um Rekonstruktionen. Für Berlin-Cölln ist kein Plan aus dem Mittelalter überliefert. Die früheste Darstellung überhaupt ist eine Ansicht der Silhouette der Stadt um 1537 von Nordnordost gesehen.

Im frühesten bekannten Stadtplan – von Johann Gregor Memhardt um 1650 aufgezeichnet – sind beide Städte mit einer Mauerund Grabenanlage umgeben. Der Stadtplan des Ingenieurs Memhardt
(1607–1678), dem kurfürstlichen Festungsbaumeister, zeigt zum ersten Mal die Stadtgebiete von Cölln und Berlin und deren wichtigste Gebäude.

Das Kloster der Franziskaner, »Graues Kloster« genannt, von Stridbeck um 1690 gezeichnet.

Deutlich wird das Zentrum von Cölln von der Gertraudenstraße mit dem Fischmarkt gebildet. Hier befanden sich die Petrikirche und das Cöllnische Rathaus. Auf der Berliner Seite dominierten die Nikolai- und die Marienkirche, dazwischen lag das erste Berliner Rathaus. In beiden Städten hatten sich auch die großen Mönchsorden niedergelassen: die Dominikaner in Cölln und die Franziskaner in Berlin. Die Zentren von Cölln und Berlin waren über den Mühlendamm, eine mit Wassermühlen besetzte Staumauer verbunden. Sie war wahrscheinlich für lange Zeit die einzige Verbindung zwischen beiden Städten, die sich im Jahre 1307 zu einer Städte-Union zusammenschlossen.

Johann Gregor Memhardt:
(1607 in Linz–1678 in Berlin)
Um 1622 emigrierte die protestantische Familie nach Holland, wo Memhardt vermutlich seine Ausbildung als Festungsbauingenieur begann. Spätestens 1640 trat er in brandenburgischen Dienst, er arbeitete am Festungsbau von Pillau sowie bei einigen Bauwerken in der näheren
Umgebung mit. Zwischen 1640 und 1650 unternahm er als »Reise-Ingenieur« des Kurfürsten mehrere Reisen nach Holland.

1650 bekam Memhardt eine Anstellung in Berlin und erlangte im Jahr 1656 die Aufsicht über alle kurfürstlichen Gebäude. Zwei Jahre später wurde Memhardt Direktor der Festungswerke. Da seine
Aufgaben in der Kurmark und beim Schlossbau in Berlin immer umfangreicher wurden – 1664 wurde er Lehrer des Kurprinzen Karl Aemil – gab er die administrative Leitung des Festungsbaus ab.

Sein Wirken bekam einen anderen Schwerpunkt: Memhardt wurde im Mai 1669 Gemeindevorsteher und im November 1669 gemeinsam mit Plesse Bürgermeister des Friedrichwerders. Von seinen zahlreichen Werken ist heute keines mehr erhalten, die meisten waren bereits vor dem Zweiten Weltkrieg verschwunden. Er ist verantwortlich für das Lusthaus »Grotte« im Lustgarten (1650), verschiedene Arbeiten am Schloss von Berlin, die ersten Wohnhäuser auf dem Friedrichswerder und die 1658 nach seinen Entwürfen begonnene Festungsanlage Berlins. Am Schloss von Potsdam wirkte er ebenfalls mit.