Koliņko begon zijn carrière bij Skonto FC en speelde onder meer in Engeland voor Crystal Palace en in Rusland voor FK Rostov en Roebin Kazan. Drie seizoenen lang speelde hij bij Roebin; in zijn laatste seizoen daar (2007/08) werd hij voor het eerst in zijn carrière landskampioen. Vanaf 2015 speelde hij voor Baltika Kaliningrad. In 2014 werd Koliņko uitgeroepen tot Lets voetballer van het jaar. Hij besloot zijn loopbaan in 2015 bij FK Spartaks Jūrmala. Daar werd Koliņko in 2015 kort interim hoofdtrainer. Vervolgens werd hij keeperstrainer. Dat was hij in 2017 ook bij FK Sjachtsjor Salihorsk en in 2018 werd hij assistent-trainer bij RFS.
Hij kwam sinds 1997 uit in het Lets voetbalelftal. Met Letland nam Koliņko deel aan het Europees kampioenschap voetbal 2004, waar de groepsfase niet overleefd werd na verlies van Nederland en Tsjechië en een gelijkspel tegen Duitsland. Na zijn 86ste interland in juni 2010 kwam Koliņko ruim drie jaar lang niet in actie voor zijn land, tot hij in september 2013 weer werd opgeroepen voor het kwalificatietoernooi voor het WK 2014. Op 16 november 2014 incasseerde hij tot op dat moment de meeste tegendoelpunten in een interland, toen in en tegen Nederland met 6–0 werd verloren. In de 92 daaraan voorafgegane interlands was Koliņko nooit eerder meer dan viermaal gepasseerd.
