Po zaliczeniu końcowych egzaminów Kołodin został skierowany do programu Woschod.W 1965 brał udział w szkoleniu do lotu statku kosmicznego Woschod 2. Dostał przydział do trzeciej załogi razem z Wiktorem Gorbatko.Od września 1965 do grudnia 1968 wraz z grupą innych kosmonautów uczestniczył w programie Kontakt. Jego celem było wypróbowanie na orbicie okołoziemskiej systemu dokowania dwóch statków kosmicznych. Misje miały być realizowane w ramach radzieckiego programu załogowych lotów na Księżyc. Kołodin trenował początkowo z Andrijanem Nikołajewem i Wiktorem Gorbatko, a później Władimirem Szatałowem oraz Władisławem Wołkowem. Szatałowa zmieniali później kolejno Anatolij Filipczenko i Anatolij Kuklin.W 1969 brał udział w przygotowaniach do grupowego lotu trzech statków kosmicznych: Sojuz 6, 7 i 8. Razem Władimirem Szatałowem oraz Aleksiejem Jelisjejewem był w załodze dublerów statku Sojuz 7.Na początku 1970 powrócił do programu Kontakt i razem z Gieorgijem Dobrowolskim tworzył jedną z trenujących załóg.Od września 1970 do kwietnia 1971 uczestniczył w przygotowaniach do lotu statku Sojuz 10 na pierwszą załogową stację kosmiczną typu Salut. Był inżynierem-badaczem w załodze dublerów, którą dowodził Aleksiej Leonow. Funkcję inżyniera pokładowego pełnił natomiast Walerij Kubasow.