W grudniu 1998 r. Krikalow wraz z Robertem Cabaną jako pierwsi przycumowali do Międzynarodowej Stacji Kosmicznej. Swój pobyt rozpoczęli od zapalenia świateł w jej pierwszym komponencie – amerykańskim module Unity.
W dniach od 4 do 15 grudnia 1998 r. Krikalow brał udział w locie STS-88 Endeavour – pierwszej misji montażowej na Międzynarodowej Stacji Kosmicznej. W ciągu 12 dni trwania misji, moduł Unity zintegrowano z rosyjskim modułem Zaria. Dwaj członkowie załogi wykonali trzy spacery kosmiczne, w toku których połączyli przewody i zainstalowali narzędzia/sprzęt do użytku w późniejszych spacerach kosmicznych. Załoga dokonała rejestracji swoich działań za pomocą kamer IMAX. Ponadto zainstalowali dwa satelity, a mianowicie: Mighty Sat 1 i . Misja trwała 283 godziny i 18 minut.
Międzynarodowa Stacja Kosmiczna mały|Krikalow zakłada treningowy skafander kosmiczny
Krikalow był członkiem załogi biorącej udział w Ekspedycji 1. Start nastąpił 31 października 2000 r. na pokładzie statku Sojuz, wystrzelonego z kosmodromu Bajkonur w Kazachstanie. Bez komplikacji dotarli na stację 2 listopada 2000 r. W trakcie pobytu na ISS mieli za zadanie przygotować wnętrze placówki orbitalnej dla kolejnych załóg.