Korolev was born in Tayshet, USSR on July 26, 1961.[1] His mother, Alexandra Vasilievna, was a teacher in Siberia, and his father worked at the construction site of the Abakan-Taishet Railway.[2] Korolev attended public school from 1968 to 1976.[2]
From 1977 to 1981, Victor studied at the S. I. Taneyev Musical Institute of Kaluga [ru] majoring in piano.[2] In 1981, he tried to attend theater school but did not succeed. By 1982, Korolev had been drafted to the Soviet Army, where he was stationed in Belarus as a private in missile forces,[1][3] where he considered himself "fortunate" to participate in the military orchestra.[2] According to Korolev, army musicians in the orchestra had special privileges including time off and the ability to see films in theater. Korolev has described the army musician life as a type of "army bohemia".[2]
In 1984, he was accepted to Mikhail Shchepkin Higher Theatre School in Moscow, from which he graduated in 1988.[1] After graduating, he worked with theatrical director Yuri Sherling [ru] and was featured in films, mostly prominently in 1990 Soviet-Italian-Spanish-Moroccan film The Battle of the Three Kings as well as 1993's Силуэт в окне напротив (lit. 'Silhouette in the opposite window') and 1993's Играем "Зомби", или Жизнь после битв (lit. 'Playing "Zombies": or, Life After the Battles').
He began recording albums from 1992 onwards.
The comedic claymation music video for Korolev's song "Базар-Вокзал" (lit. 'Bazaar Station') was released in 1997, which Korolev referred to as the first animated music video in Russia.[1][4]