Mir EO-16

Ab Februar 1994 schließlich wurde Malentschenko die Sojus-TM-19-Mannschaft unterstellt. Die Mission der 16. Stammbesatzung mit Malentschenko und Mussabajew zur Raumstation Mir begann Anfang Juli 1994 und dauerte vier Monate. Anfang September führte Malentschenko die erste manuell gesteuerte Kopplung eines Progress-Frachtraumschiffes durch und wenige Tage später verließen die beiden Mir-Raumfahrer zwei Mal die Station für zusammen elf Stunden. Als Anfang Oktober die Ablösung eintraf, hatte sie den Deutschen Ulf Merbold mit an Bord. Für ihn war es sein dritter Flug. Er lebte und arbeitete einen Monat auf Mir und kehrte dann mit Malentschenko und Mussabajew zurück.

Im November 1994 wurde Malentschenko durch einen Erlass des damaligen russischen Präsidenten, Boris Jelzin, die Auszeichnung Held der Russischen Föderation verliehen.

STS-106

Malentschenko begann ab Oktober 1998 mit dem Training für seinen zweiten Raumflug. STS-101 war eine Mission des Space Shuttle und sollte im Herbst 1999 durchgeführt werden. Malentschenko war als Missionsspezialist für die Crew eingeteilt und reiste deshalb in die USA nach Houston in Texas. Im Frühjahr 2000 teilte die NASA die Aufgaben und die Besatzung von Flug STS-101 auf: STS-106 wurde aus der Taufe gehoben und drei Raumfahrer der alten Mission (Malentschenko, Morukow, Lu) auf STS-106 gesetzt. Mit diesen beiden Flügen, direkt hintereinander im Abstand von vier Monaten durchgeführt, sollte die Internationalen Raumstation (ISS) schneller für die Aufnahme ihrer ersten Besatzung vorbereitet werden. Während seines zweiten Fluges im September 2000 stieg Malentschenko zusammen mit Lu am dritten Tag für sechs Stunden aus, um Kabel zu verlegen und einen Instrumentenausleger zu montieren.

ISS-Expedition 7

Nachdem Malentschenko und Lu auf STS-106 so effektiv zusammengearbeitet hatten, entschieden sich die Verantwortlichen, das Duo für einen Langzeiteinsatz auf der ISS zu ernennen. Seit Januar 2001 bereiteten sie die beiden Raumfahrer auf ihren Flug als ISS-Expedition 7 vor. Mit Sojus TMA-2 brachen sie Ende April 2003 zur ISS auf. Ursprünglich hatte ein weiterer Raumfahrer (erst Sergei Moschtschenko, dann Alexander Kaleri) zur Besatzung gehören sollen, und alle drei sollten mit STS-114 zur ISS gebracht werden. Als nach dem Unglück der Columbia im Februar 2003 vorübergehend die Space-Shuttle-Flüge zur ISS ausgesetzt wurden, hatte man alle folgenden Stammbesatzungen auf zwei Personen reduziert, um Ressourcen zu sparen, und war gezwungen, alle Zubringerflüge per Sojus-Rakete durchzuführen. Kommandant Malentschenko und Bordingenieur Lu blieben ein halbes Jahr an Bord der Raumstation und kehrten im Oktober 2003 mit dem Sojus-Raumschiff wieder zur Erde zurück.

ISS-Expedition 16

Malentschenko war Bordingenieur der ISS-Expedition 16, die im Februar 2007 offiziell ernannt wurde. Der Start erfolgte am 10. Oktober 2007 mit Sojus TMA-11. Die Landung fand am 19. April 2008 nach 192 Tagen ebenfalls mit Sojus TMA-11 statt.

ISS-Expeditionen 32 und 33

Malentschenko schied am 27. Juli 2009 aus dem Kosmonauten-Korps aus, kehrte aber am 9. Februar 2010 wieder zurück. Er war in der Reservemannschaft für Sojus TMA-03M, dessen Start Ende 2011 stattfand. Am 15. Juli 2012 startete Malentschenko als Kommandant des Raumschiffes Sojus TMA-05M zur ISS. Als er am 17. Juli 2012 in die ISS umstieg, war er erst der dritte Raumfahrer und davon der erste Russe, der die Station zum vierten Male besucht. Er arbeitete dort als Bordingenieur der ISS-Expeditionen 32 und 33. Am 19. November 2012 kehrte er zusammen mit Sunita Williams und Akihiko Hoshide auf die Erde zurück. Mit über 641 Tagen lag er damit auf Platz 7 der Raumfahrer mit der längsten Gesamtdauer im All.

ISS-Expedition 46 und 47

Malentschenkos sechster Einsatz startete am 15. Dezember 2015. Als Kommandant des Raumschiffes Sojus TMA-19M stattete er der ISS zusammen mit dem britischen ESA-Astronauten Timothy Peake und dem NASA-Astronauten Timothy Kopra seinen fünften Besuch ab. Dort arbeitete er als Bordingenieur der Expeditionen 46 und 47. Mit Peake und Kopra kehrte er am 18. Juni 2016 zur Erde zurück. Mit diesem Flug ist Malentschenko nach Sergei Krikaljow der zweite russische Kosmonaut mit sechs Raumflügen und der erste Raumfahrer, der fünf Mal zur ISS flog. Mit diesem Flug hatte Malentschenko insgesamt 827 Tage im All verbracht. Nur Gennadi Padalka mit 878 Tagen hat noch mehr Weltraumerfahrung als er.

Malentschenko verließ das Kosmonautenkorps am 2. September 2016.