Kolyvanov kwam in totaal 35 keer uit voor de nationale ploeg van Rusland (twaalf goals) in de periode 1992-1998. Onder leiding van bondscoach Pavel Sadyrin maakte hij zijn debuut op 14 oktober1992 in de WK-kwalificatiewedstrijd tegen IJsland (1-0). Hij viel in dat duel na 77 minuten in voor Sergej Joeran. Kolyvanov nam met Rusland deel aan het EK voetbal 1996 in Engeland, waar de ploeg in de eerste ronde werd uitgeschakeld.