Im Frühjahr 1988, nach den Ereignissen im Zusammenhang mit der Liebknecht-Luxemburg-Demonstration im Januar, kam Gutzeit zu der Einsicht, dass die bisherige Arbeit der Opposition in der DDR praktisch gescheitert sei. Der Initiative Frieden und Menschenrechte (IFM) zum Beispiel warf er vor, keine klaren politischen, auf die Systemüberwindung orientierten Ziele zu haben. Die Arbeit müsse insgesamt neu orientiert und organisiert werden. Martin Gutzeit arbeitete gemeinsam mit Markus Meckel ein Vereinsprojekt „Bürgerbeteiligung“ aus. Satzungsziel sollte die Herstellung einer demokratischen Öffentlichkeit, die Demokratisierung und Pluralisierung der Gesellschaft sein, was auf die Abschaffung der kommunistischen Diktatur hinauslief. In diesem Projekt fanden die Erfahrungen und Ideen der letzten Jahre zusammen. Vom Ansatz ähnelte diese Idee den späteren Bürgerbewegungen wie Neues Forum und Demokratischer Aufbruch.
Bei seiner Beschäftigung mit Hegels Philosophie kam Gutzeit immer mehr zu dem Schluss, dass die ihn umgebende Wirklichkeit nicht nur aufgebrochen werden müsse, sondern dass dies auch möglich sei. Jahre später schrieb er einmal über diesen Erkenntnisprozess: „Ich verhehle nicht, dass mich eine euphorische Stimmung erfasste, als ich glaubte, eine Gegenlogik gegen die scheinbar unüberwindlichen Machtverhältnisse gefunden zu haben, denen ich mich bis dahin ziemlich ohnmächtig ausgeliefert fühlte.“ Zugleich überkamen ihn aber auch Zweifel, ob mit einem Verein tatsächlich das Gewaltmonopol des Staates entscheidend herausgefordert werden könne. Gutzeit war im Gegensatz zu vielen anderen Oppositionellen kein prinzipieller Gegner des Staates – sehr wohl aber des totalitären Staates. Vor diesem Hintergrund reifte immer stärker die Einsicht, nur mit einer neuen Partei wirklich etwas bewegen und Staat wie Gesellschaft demokratisieren zu können.
Mit Markus Meckel, der sogleich angetan war, besprach er die Idee. Als Meckel im Februar 1989 auf einem Oppositionstreffen erste vage Überlegungen zur Gründung einer Partei vortrug, wurden diese abgelehnt. Ein solches Vorhaben überforderte die meisten Oppositionellen noch erheblich. Weder Markus Meckel noch Gutzeit waren von dieser Ablehnung sonderlich überrascht, kannten sie doch – wie sie sagen würden – „ihre Pappheimer“.
Gutzeit und Meckel ließen sich jedoch nicht beirren, in den folgenden Wochen und Monaten reifte ihre Idee immer weiter. Im Juli 1989 entstand der Aufruf zur Gründung der Sozialdemokratischen Partei in der DDR (SDP), der am 26. August der Öffentlichkeit vorgestellt wurde. In oppositionellen Kreisen war die Initiative bereits vorher bekannt gemacht worden. Den Aufruf unterschrieben neben Gutzeit und Meckel auch der Theologe Arndt Noack, ein alter Studienfreund der beiden, sowie Ibrahim Böhme, der 1990 als einflussreicher Inoffizieller Mitarbeiter (IM) des MfS enttarnt wurde. Gutzeit hatte schon in den 80er Jahren eine Reihe von Maßnahmen entwickelt, um IMs zu enttarnen und sich und sein Umfeld, so dies überhaupt möglich war, vor der Staatssicherheit zu schützen. Böhme war ihm zwar stets suspekt, aber Gutzeit hatte keine Beweise in der Hand, weshalb er nichts unternehmen konnte.
Dass Gutzeit und Meckel eine sozialdemokratische Partei gründeten, war kein Zufall. „Freiheit, Demokratie, soziale Gerechtigkeit, der Begriff der Solidarität waren für uns eine Selbstverständlichkeit in unserer Tradition, und ökologische Aspekte“, sagte Gutzeit Anfang der 90er Jahre. Außerdem studierte Gutzeit in der zweiten Hälfte der 80er Jahre die Geschichte der europäischen Sozialdemokratie. Für ihn bestanden keine Zweifel, dass eine soziale Marktwirtschaft, so wie sie die Sozialdemokratie in Europa nach 1945 vertreten hatte, die beste Alternative für die DDR wäre. Hinzu kam der unübersehbar provokative Ansatz, mit einer sozialdemokratischen Partei in der DDR die SED besonders herauszufordern und ihr ihren Machtanspruch streitig zu machen.
Gutzeit und Meckel zählen nicht zu der Sorte Revolutionäre, von denen es heißt, sie verlegten den Umsturz auf das Wochenende und in die Feierabendstunden. Als sie ihre Unternehmung „SDP-Gründung“ – mit einer durchaus angenehmen Portion Größenwahn – angingen, konnten sie nicht wissen, wie dies enden und vor allem nicht, wie schnell alles gehen würde. Eigentlich wartete auf die beiden für viele Jahre das Zuchthaus und anschließend die Fahrt gen Westen ohne Rückfahrtschein. Dass es anders kam, lag an vielen Faktoren, die zusammen die Revolution schnell und erfolgreich ausbrechen und siegen ließen. Martin Gutzeit hat dazu einen wichtigen Beitrag geleistet. Er und seine Freunde von der SDP waren die ersten, die mit der SED nicht nur in einen Dialog treten, sondern ihr die Macht entreißen wollten. Davon lernten schnell auch viele andere, weshalb die Revolution bald unumkehrbar wurde.
Es war nicht nur eine symbolische Idee, dass die Parteigründung der SDP ausgerechnet am 7. Oktober 1989, als die SED-Führung den 40. Jahrestag der DDR feiern wollte, in Schwante bei Berlin erfolgte. Die Aufregung in Berlin versprach den Gründungsmitgliedern die Chance, etwas weniger beobachtet zu werden – dies glaubte Martin Gutzeit jedenfalls. Für manche war es dann dennoch ein echtes Abenteuer, nach Schwante zu kommen und den MfS-Observateuren zu entfliehen.
Nach diesem Gründungsparteitag war Gutzeit in den nächsten Monaten an allen wichtigen Entscheidungen und Handlungen der Opposition beteiligt. Er war kein Mann der Öffentlichkeit, sondern einer, der beharrlich im Hintergrund die Fäden zog und diese auch oft genug in den Händen hielt. In der ersten frei gewählten Volkskammer war er parlamentarischer Geschäftsführer der SPD-Fraktion. Nach einer kurzen Übergangszeit im Bundestag (1990), einer Assistenz an der Theologischen Fakultät der Humboldt-Universität zu Berlin (1991) und einer einjährigen Werkvertragszeit bei der Friedrich-Ebert-Stiftung, trat Gutzeit zum Januar 1993 das neu geschaffene Amt des Berliner Landesbeauftragten für die Stasi-Unterlagen an. Dieses Wahlamt hatte er bis 2017 inne.
Gutzeit hat 1992–98 in den beiden Enquete-Kommissionen des Bundestages, die sich mit der Aufarbeitung und den Folgen der SED-Diktatur beschäftigten, als Sachverständiger mitgearbeitet. Wiederum gemeinsam mit Markus Meckel hatte er die Idee zur Einsetzung dieser Kommissionen überhaupt erst entwickelt. Das geschah in Abwehr anderer kursierender Vorschläge, etwa zur Errichtung außerparlamentarischer Tribunale.
Martin Gutzeit hat zwei erwachsene Kinder und ist mittlerweile auch Großvater. Schon mit seinem Vater saß er gern auf der gemütlichen Veranda, um über „Gott und die Welt“ zu plaudern. So weiß er auch heute zu genießen, sei es in der Politik, der Musik, bei Hegel und Aristoteles oder auf seinen kulturhistorischen Reisen, die ihn in jenes alte Europa führen, das er jahrzehntelang nur theoretisch studieren konnte. Nun, da vorerst keine neue Revolution geplant zu werden braucht, rücken auch allmählich die alten Hegel-Studien wieder stärker in den Vordergrund. Es bleibt abzuwarten, was Martin Gutzeit diesmal für eine politische Lehre daraus ziehen wird.