Milenkov was the Soviet Premier for years. Some time before he became Premier, Milenkov became the leader of the Blisk and hinted that this was the same case with all of the Soviet Leaders before him.
At the beginning of the game, Milenkov was first mentioned in the opening scene by Ivan Oranchov, who gave a slide show presentation to his fellow agents, Milenkov included, about the actions of the Furons Cryptosporidium and Orthopox. Milenkov placed Oranchov in charge of the mission to start an American Revolution and to distribute Revelade. Oranchov ultimately failed and was killed by Crypto in the Tunnel network in Albion.
Milenkov appeared on a large screen when Natalya and Crypto infiltrate a KGB Base inside a volcano in Takoshima. Broadcasting from Tunguska, Milenkov revealed his ultimate plan in Takoshima: in the base, he created a Godzilla-like beast, Kojira (based off Godzilla), and unleashed it upon Takoshima. After he defeated Kojira, Crypto traveled with Natalya to Tunguska to find Milenkov.
Milenkov was not seen until Crypto found Natalya captured at a Blisk Base that was located at a crashed Blisk Warship. After Crypto destroyed the warship, Milenkov appeared and told him that Project Solaris was on the Moon. He then bid Crypto and Natalya farewell and escaped in a Blisk Shuttle. Crypto rescued Natalya and the two traveled to the Moon.
Milenkov met Crypto at one of the KGB Bases. After Crypto destroyed everything in it, Milenkov entered and monologued about his "Master Plan": he intended to flood Earth into a radioactive ocean paradise for all Blisk to live in. He then left and did not appear again until the final mission. After Crypto and Natalya destroyed the Blisks' main hive, they were about to share a kiss. Milenkov appeared and shot Natalya in the back, which killed her. He then mutated into a Blisk and fought Crypto. Crypto managed to kill Milenkov and, afterwords, cloned Natalya. After Milenkov's death, Crypto destroyed all of the surviving Blisk. It was unknown what happened to the Soviet Union after Milenkov's defeat, but it most likely survived, because it was said by the news broadcaster in a Sunnywood mission in Path of the Furon that: "The fragile peace of the Cold war has ended as Soviet Jets bomb Sunnywood today" however, the American Government most likely didn't believe her, because no war actually happened, and would surely have been hinted at somewhere in the game.
In his human form, Milenkov had white hair and a blind left eye with a long scar that ran down it. Milenkov wore a high ranking KGB Uniform that possessed badges, stars, and a purple robe that showed his authority. In that form, Milenkov appeared to be a parody of James Bond Villain, Ernst Stavro Blofeld, in You Only Live Twice: Milenkov was first revealed in the mission You Only Live 137 Times and Blofeld also had a volcano base, that was also located in Japan. In his Blisk form, Milenkov had dark blue skin plated with dark red armor; that color scheme was the same as his KGB space suit. Milenkov had a cannon mounted on both his arm and back and both fired green blasts of energy.