30. ledna 1996 bylo oficiálně oznámeno složení první stálé posádky mezinárodní orbitální stanice. Velitelem tříčlenného týmu měl být Američan Bill Shepherd, s nímž měli necelý půlrok trávit v prostorách stanice Jurij Gidzenko a… Sergej Krikaljov. Let měl odstartovat v květnu roku 1998. Ovšem záhy se objevily problémy s financováním ruské části stanice. Stavba servisního modulu Zvezda, který měl pro plánovaný komplex zajistit zázemí a pohonný systém, byla v roce 1996 v takovém skluzu, že Rusko nebylo schopno garantovat plánovaný start v dubnu 1998. Celá mašinérie ISS se tím pádem zastavila a posádka Shepherd-Gidzenko-Krikaljov byla nucena přerušit výcvik. Sergej pak v roce 1998 na palubě raketoplánu Endeavour při misi STS-88 asistoval při sestavování prvních komponentů stanice. 12. června 2000 pak tak dlouho očekávaná Zvezda zamířila na orbit, aby se v automatickém režimu spojila se zadním portem modulu Zarja, toho času spojeného s americkým modulem Unity. Základ ISS byl konečně pohromadě a mohla se začít připravovat první stálá posádka. A protože nebylo efektivní cvičit posádku úplně ‚od píky‘, svých rolí se opět ujali Shepherd, Gidzenko a Krikaljov. Pro posledně jmenovaného to měl být už pátý start do vesmíru…

Nová doba, nové možnosti, nové plány. A také staronoví partneři – to vše přinesl počátek devadesátých let ruské kosmické agentuře. Rusko a Spojené státy se ocitly překvapivě v pozici spolupracujících velmocí. Oba státy měly co nabídnout a oběma chyběly přesně ty dílky skládačky, které měl v ruce jejich nový partner. Spojené státy už přes deset let uvažovaly o velké orbitální stanici, ale chyběly jim peníze i zkušenosti – po konci studené války se konaly velké škrty v rozpočtu, Skylab byl dávnou minulostí a úroveň poznání od té doby pokročila. Rusko zase mělo zkušenosti a (víceméně) funkční stanici, ale scházely finance. Navíc hrozil odliv mozků z ruského kosmického a raketového průmyslu směrem ke státům s ne zcela dobrou pověstí. Obě mocnosti se rozhodly spolupracovat a pokusit se spojit své úsilí tak, aby byl výsledek přínosem oběma stranám. Zda tomu tak nakonec bezezbytku bylo, to ponechme v tuto chvíli stranou, každopádně v červnu 1992 oznámili Boris Jelcin a George Bush záměr uskutečnit společný program, zvaný “Dohoda mezi Spojenými státy americkými a Ruskou federací ohledně spolupráce na výzkumu a využití kosmického prostoru pro mírové účely“. Konkrétním výstupem této dohody měly být krátkodobé lety dvou ruských kosmonautů na americkém raketoplánu a jeden dlouhodobý let Američana na Miru. Na přelomu léta a podzimu 1992 začalo v zákulisí ruské agentury hledání vhodných kandidátů pro let na Shuttlu. Nakonec se v hledáčku ocitli dva zkušení kosmonauti…