Die Anfänge des Stadtarchivs Frankfurt (Oder) reichen bis in das 13. Jahrhundert zurück, als der brandenburgische Markgraf Johann I. den Marktflecken an der Oder zur Stadt erhob. Im 14. Jahrhundert erwählten die Kurfürsten aus dem Haus Wittelsbach das rathäusliche Archiv zum Aufbewahrungsort wichtiger Urkunden der brandenburgischen Landesherrschaft. Als rathäusliche Organisationseinheit diente das Archiv in erster Linie der städtischen Regierung und Verwaltung. Neben der Ratsstube befanden sich "elf verschließbare Spinde, ‚darin nach dem ABC die Akten verwahret‘" waren. Die Urkunden lagerten in einem verschlossenen eisernen Privilegienkasten. Mit der Einführung des "Rathäuslichen Reglements" im Jahr 1719, wurde sprachlich erstmals zwischen kurrentem Schrift- und älterem Archivgut unterschieden. War bislang die "Registratur bey dem Rathause" Sache des Secretarius, wurde nun zusätzlich ein Registrator eingestellt, der dafür zuständig war, dass die "Alten als Neuen Sachen" nicht in "Confusion und Unordnung" gerieten. Bemühungen um eine Erschließung hat es stets gegeben. Das älteste heute vorhandene Archivalienverzeichnis stammt aus dem Jahr 1546. Der brandenburgische Kurfürst und preußische Herzog Friedrich Wilhelm ordnete 1653 an, "alle Registraturen, Bücher und Documenta [...] mit Fleiß [...] verzeichnen zu lassen". Als erster externer Nutzer gilt der Frankfurter Universitätsprofessor Johann Christoph Beckmann (1641-1717), der die städtischen Archivalien in seiner Tätigkeit als Stadt- und Landeshistoriker auswertete.
Eine Professionalisierung des städtischen Archivwesens setzte erst im 19. Jahrhundert ein. Justizkommissarius Heinrich Karl Ludwig Bardeleben (1775-1852) fand das Archivgut im Jahr 1822 auf dem Dachboden des Rathauses "als einen Haufen mit Schmutz vermischter Bücher, Papiere, Blätter" vor. Eine fachgerechte Erschließung und Magazinierung erfolgte Ende der 1880er Jahre, nachdem Oberbürgermeister Hermann Friedrich Wilhelm von Kemnitz dem Preußischen Geheimen Staatsarchiv in Berlin das städtische Archivgut zur Übergabe anbot. Generaldirektor der preußischen Archivverwaltung Heinrich Karl Ludolf von Sybel berief in Abstimmung mit der Frankfurter Regierung eine Archivkommission ein, die das städtische Archivwesen untersuchte. Zwar schlug auch der Abschlussbericht der Kommission die Übergabe als Depositum vor, aber sowohl die Stadtverordneten als auch die Mitglieder des Historischen Vereins sprachen sich für den Verbleib der Archivalien in Frankfurt aus. In der Folge verpflichtete die preußische Archivverwaltung den Magistrat, für geeignete Räume und ausgebildetes Personal zu sorgen. Für die Erschließungsarbeiten war Dr. Robert Arnold vom Preußischen Geheimen Staatsarchiv mehrmals für mehrere Monate nach Frankfurt abgeordnet worden. Arnold erarbeitete eine erste Archivordnung, begleitete den Umzug des Archivgutes aus dem Rathaus in die Sakristei der Franziskanerklosterkirche und öffnete das Archiv für externe Nutzungen. Zudem leitete er Mitarbeiter der Stadtverwaltung in der Aussonderung und Archivierung nicht mehr benötigter Unterlagen an. Erster von der Stadt besoldeter Archivar wurde der Gymnasialprofessor Dr. Adolf Gurnik. Unter seinen Nachfolgern Gymnasialprofessor Dr. Reinhold Kubo (Stadtarchivar 1903-1925) und Dr. Bruno Binder (Stadtarchivar 1925-1945) zog das Stadtarchiv zunächst in das Rektoratsgebäude der alten Frankfurter Universität und schließlich in den ausgebauten Turmstumpf der Marienkirche um.