Lot został jednak ostatecznie odwołany w momencie zakończenia programu Woschod.
Po zakończeniu wspomnianego programu Szatałow zaczął przygotowania do lotów na statkach kosmicznych typu Sojuz.
26 października 1968 r. został dublerem G. Bieriegowoja, który udał się w kosmos na statku kosmicznym Sojuz 3.
Pierwszy lot kosmiczny odbył w 1969 roku. 14 stycznia wyruszył w kosmos jako dowódca Sojuza 4. Dzień później na orbicie znalazł się drugi radziecki statek kosmiczny Sojuz 5 z trzyosobową załogą – Borys Wołynow, Aleksiej Jelisiejew i Jewgienij Chrunow. 16 stycznia doszło do połączenia obu statków i dwaj kosmonauci Jelisiejew i Chrunow poprzez otwarty kosmos przeszli na pokład Sojuza 4. Był to manewr wykonany po raz pierwszy w historii załogowych lotów kosmicznych. Wraz ze swoimi kolegami Szatałow wylądował na Ziemi 17 stycznia 1969 roku. Przebywał w kosmosie przez 2 dni 23 godziny 20 minut i 47 sekund. Jego koledzy z załogi o dobę krócej.