In his human form, Milenkov has white hair and a blind left eye with a long scar running down it. He wears a high ranking KGB uniform possessing badges and stars and a purple robe to show his authority. In this form, he appears to be a parody of the James Bond villain Ernst Stavro Blofeld, as seen in You Only Live Twice. Milenkov is first revealed in the mission You Only Live 137 Times. Blofeld also had a volcano base, located in Japan. In his Blisk form, he has dark blue skin plated with dark red armor; this color scheme is the same as his KGB space suit. He has a cannon mounted on his arm and back, both of which fire green blasts of energy.
Milenkov was the Soviet Premier for years. Some time before he became Premier, he became the leader of the Blisk, and he hints that this was the same case with all Soviet leaders before him.
In the game, he is first mentioned in the opening scene by Agent Oranchov, who is giving a slide show presentation to his fellow agents, Milenkov included, about the actions of the Furons Cryptosporidium and Orthopox. He places Oranchov in charge of the mission to start an American revolution and to distribute Revelade. Oranchov ultimately fails and is killed by Crypto.
Milenkov appears on a large screen when Natalya Ivanova and Crypto infiltrate a KGB base inside a volcano in Takoshima. Broadcasting from Tunguska, Milenkov reveals his ultimate plan in Takoshima: in the base, he had created a Godzilla-like beast, Kojira (based off Godzilla), and unleashed it upon the island. After defeating Kojira, Crypto travels with Natalya to Tunguska to find Milenkov.
The Soviet Premier is not seen until Crypto finds Natalya captured at a Blisk Base located at a crashed Blisk Warship. After Crypto destroys the warship, Milenkov appears and tells him that Project Solaris is on the Moon. He then bids Crypto and Natalya farewell and escapes in a Blisk Shuttle. Crypto rescues Natalya and the two travel to the Moon.
Milenkov meets Crypto at one of the KGB bases. After Crypto destroys everything in it, Milenkov enters and monologues about his "Master Plan"; he intends to flood the Earth into a radioactive ocean paradise for all Blisk to live in. He then leaves and does not appear again until the final mission. After Crypto and Natalya destroy the Blisks' main hive, they are about the share a kiss. Milenkov appears and shoots Natalya in the back, killing her. He then mutates into a Blisk and fights Crypto. Crypto manages to defeat him and afterwords, clone Natalya. After his death, Crypto destroys all surviving Blisk. It is unknown what happens to the Soviet Union after Milenkov's defeat, but it most likely survives, because it is said by the news broadcaster in a Sunnywood mission in DAH: 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 doesn't believe her, because no war actually happens, and it would surely be hinted somewhere in the game.