Rodák z ukrajinské Oděsy . Absolvoval tamní Nejdanovu konzervatoř pod vedením Nikolaje Ogreniče. Po studiích debutoval v oděské opeře Aleko S. Rachmaninova. V letech 1995-1997 byl sólistou Nové opery v Moskvě, kde debutoval ja Leicester v Donizettiho Marii Stuartovně. Je vítězem několika mezinárodních pěveckých soutěží včetně soutěže Franciska Vinase v Barceloně a získal třetí cenu v kategorii a zvláštní cenu v kategorii zarzuela v prestižní soutěži Plácida Dominga Operalia (2000). K. Andrejev zahájil mezinárodní kariéru rolí Rodolfa (Luisa Mileler) v Montpellier, Frankfurtu a v Lausanne. Od té doby hostuje v mnoha operních domech a koncertních síních v Severní Americe (Washington Opera), Austrálii (Melbourne, Brisbane) a v Evropě (Londýn, Paříž, Nancy Frankfurt, Lipsko, Lausanne Klagenfurt, Lisabon, Teatro dell´Opera v Římě, Teatro Regio di Torino, Teatro Bellini di Catania, Teatro Petruzzelli di Bari, Teatro la Fenice di Venezia, Opera Monte Carlo) a vystupoval na mnoha festivalech (Festival di Torre del Lago Puccini, Dordrecht Festival v Holandsku, Wexford Festival ad.) Od r. 2013 sólista Oděského národního akademického divadla opery a baletu.