Kolcana Soviet nace en el 2000, por iniciativa de David, ex bajista de El Furibundo Serna, y Claudia, quien estuvo anteriormente en las bandas de ska La Severa Matacera y Los Santos Indeseables y había organizado un proyecto de banda femenina que no se llegó a presentar en público. De ese proyecto, Claudia y David llaman a Sandra, la baterista y completan la banda con Mauricio, ex integrante de Sabotaje.

En los primeros ensayos de Kolcana Soviet llega a participar Alex (ex La Severa Matacera, Santos Indeseables y Furibundo Serna), pero abandona el grupo a las pocas semanas. Con esta formación básica (Claudia en la voz, Sandra en la batería, David en el bajo y Mauricio en la guitarra) participan en el Carnaval de Britalia 2000, con un repertorio de versiones con un sonido punki de influencias mod.

En el 2001 se integra el "Pollo", también salido de Sabotaje, a reforzar la banda con el teclado. Luego se une José Mario, del mismo combo, en la guitarra líder. La banda logró así un sonido más contundente, pero los tres ex Sabotaje deciden emprender nuevos rumbos y dejan la banda. Tras un corto receso, Zoraida asume los coros, y Diego, del Sistema Sonoro Skartel, toma la guitarra y se abre una nueva etapa de Kolcana Soviet, cumpliendo la consigna de la banda inglesa Redskins: "Cantar como las Supremes y andar como los Clash".

El 13 de agosto de 2002 graban su primer tema en estudio: "¡A casa!", como parte de una recopilación internacional en homenaje a Kortatu.

El 2003 no fue un año de mucha actividad, y después de un largo receso, vuelven a tocar incorporando al "niño punk" Juan Felipe en la guitarra rítmica. Así en el 2004 hacen varios conciertos, pero entran en nuevo receso a finales de 2005...

En el primer semestre de 2007, Sandra graba pistas de batería de la mayoría de temas del repertorio, antes de partir hacia Australia. A comienzos de 2009, con Juan Felipe de nuevo en Colombia, se retoma la grabación con sus temas. Se incorporan Antonio en la guitarra y Kike en la batería, y parece que la banda toma un nuevo impulso.