Der Start erfolgte vom Kosmodrom Baikonur. Sojus 4 landete 40 km nordwestlich von Karaganda.

Der Start musste erstmalig in der sowjetischen Raumfahrtgeschichte wegen schlechten Wetters verschoben werden (geplant war der Start für den 13. Januar 1969). Es erfolgte eine Kopplung mit dem wenig später gestarteten Raumschiff Sojus 5, wobei Sojus 4 die aktive Rolle übernahm. Es war damit das erste Docking von zwei bemannten Raumschiffen, die sowohl mechanisch als auch elektrisch miteinander verbunden waren. Es gab aber keine Durchstiegsluke zum jeweils anderen Raumschiff. Der Umstieg der Kosmonauten Jewgeni Chrunow und Alexej Jelissejew musste durch einen Weltraumspaziergang zu Sojus 4 erfolgen. Dazu musste die Sojus 4-Kapsel zunächst drucklos gestellt werden, damit die beiden Kosmonauten auch einsteigen konnten.

Das sowjetische Fernsehen übertrug die Vorbereitungen zum Weltraumausstieg live. Jewgeni Chrunow und Alexej Jelissejew zogen ihre „Jastreb“-Anzüge im Orbitalmodul von Sojus 5 mit Hilfe des Kommandanten Boris Wolynow an. Mit der Entwicklung der „Jastreb“-Raumanzüge wurde 1965 kurz nach Alexej Leonows ersten problematischen Weltraumausstieg begonnen. Alexej Leonow wirkte als Berater während der Entwicklung mit, die 1966 abgeschlossen wurde. Die Herstellung und der Test erfolgte 1967 aber der Unfall mit Sojus 1 und die Kopplungsprobleme von Sojus 2 und Sojus 3 im Oktober 1968 verschoben den ersten Einsatz im Weltraum bis zu dieser Mission. Um die Probleme zu beseitigen, die den Ausstieg Alexej Leonows so problematisch haben werden lassen, nutzten die „Jastreb“-Anzüge ein Seil-Rollen-Gelenksystem. Große Metallringe um den aus Nylonstoff gefertigten Unteranzug dienten als Anker für die oberen Gelenke. Der Anzug hatte ein sich regenerierendes Lebenserhaltungssystem in einer weißen Metallkiste auf dem Bauch des Anzugs. Boris Wolynow überprüfte die Lebenserhaltungs- und Kommunikationssysteme beider Kosmonauten-Anzüge bevor er ins Kommandomodul zurückkehrte, die Verbindungsluke schloss und das Orbitalmodul dekomprimierte. Beim Ausstieg verhedderten sich Jewgeni Chrunow Halteleinen, und er schaltete versehentlich seine Anzugslüftung aus. Dies lenkte Alexej Jelissejew ab und er vergaß, die Filmkamera anzuschalten bevor er das Orbitalmodul verließ. Daher gibt es von diesem historischen Weltraumausstieg nur eine schlechte Videoaufzeichnung und keine Filmaufnahmen. Jewgeni Chrunow bewegte sich danach als Erster zum Orbitalmodul von Sojus 4 als die beiden Raumschiffe über Südamerika und damit außerhalb des Funkkontaktes zur Bodenstation waren. Alexej Jelissejew stieg um als der Komplex sich über der Sowjetunion befand.

Erst, nachdem sie im Raumschiff waren, konnte wieder der Druck hergestellt werden. Jewgeni Chrunow und Alexej Jelissejew brachten Zeitungen, Briefe und Telegramme mit, die nach Wladimir Schatalows Start gedruckt worden sind, als Beweis, dass der Transfer wirklich stattgefunden hatte.

Während des Fluges wurden zudem wissenschaftliche (medizinische und biologische) und technische Experimente durchgeführt. Letztlich waren dieses aber alles Tests für die beabsichtigte sowjetische Mondlandung.

Diese Mission bewies die Möglichkeit, dass die für das sowjetische Mondprogramm nötigen Schritte im Weltraum ausführbar waren. Der Plan sah einen einzelnen Kosmonauten vor, der über einen Weltraumaustieg vom Landemodul wieder in das Raumschiff gelangen sollte. Anders als die Apollo-Raumschiffe hatte das sowjetische Modell keinen Verbindungstunnel zwischen Lande- und Kommandomodul.

Die Kosmonauten hatten ihre Plätze im Landemodul eingenommen, nachdem sie die Luke zur Orbitalsektion geschlossen hatten. Dann richteten sie das Raumschiff so aus, dass das Triebwerk des Geräteteils in Flugrichtung zeigte. Dieses wurde kurz darauf für 188 Sekunden gezündet und leitete den Abstieg zur Erdoberfläche ein. Im nächsten Schritt erfolgte das planmäßige Abtrennen der Orbitalsektion und des Geräteteils, die beide in der Erdatmosphäre verglühten. Das verbleibende Landemodul wurde so ausgerichtet, dass der Eintrittswinkel für eine möglichst genaue Landung in Kasachstan erreicht wurde. Nach dem Eintritt in die Erdatmosphäre brach der Funkkontakt wegen der heißen Plasmagase rund um die Kapsel ab. Dann löste sich der Deckel des Fallschirmbehälters und der Bremsfallschirm wurde ausgestoßen. Nachdem auch der Hitzeschutzschild abgetrennt worden war, schwebte die Sojus an ihrem Hauptfallschirm Richtung Erdboden. Kleine Feststoff-Bremsraketen, die kurz vor dem Berühren des Bodens ausgelöst worden waren, verminderten die Aufprallgeschwindigkeit. Sofort nach der erfolgreichen Landung wurden die Fallschirmleinen gekappt, damit die Kapsel nicht durch den Wind über den Boden gezogen werden konnte. Nach der Landung gehört es zum Ritual, dass die Kosmonauten das Raumschiff mit ihrer Unterschrift versehen.
Die Landung erfolgte nur 40 km vom beabsichtigten Ziel entfernt.

Am 24. Januar 1969 sollten die Besatzungen beider Raumschiffe den damaligen KPdSU-Generalsekretär Leonid Breschnew während einer Willkommenszeremonie vor dem Moskauer Kreml treffen. Dies wurde aber durch ein Attentat auf den Sowjetführer verhindert. Der Unterleutnant Wiktor Iljin schoss acht Mal auf den Konvoi, zielte aber irrtümlich nicht auf Brechnews Auto, sondern auf das, in dem die bereits früher in den Weltraum geflogenen Kosmonauten Georgi Beregowoi, Alexej Leonow, Andrijan Nikolajew und Walentina Tereschkowa saßen. Der Fahrer des Wagen wurde getötet, ein Fahrer der Motorradeskorte, Georgi Beregowoi und Andriyan Nikolajew wurden leicht verletzt, letzterer konnte das Fahrzeug anhalten. Der Wagen Breschnews fuhr daraufhin an den auf der Tribüne wartenden Sojus 4 und Sojus 5-Besatzungen vorbei.