The Soviet Super-Soldiers were initially established by the government of the former Union of Soviet Socialist Republics as a counterpart to American teams such as the Fantastic Four and the Avengers. The program was the inspiration of Professor Piotr Phobos, a latent mutant with megalomaniacal tendencies who convinced the government establish a program designed to identify and train superhuman beings in a program called the School for Super-Soldiers. The program's first trainee was Mikhail Ursus, an orphan with the power to transform into a grizzly bear. The next two students were Nicolai Krylenko and Laynia Petrovna, children of the nuclear scientist Sergei Krylov. Other students were identified by the KGB and sent to the School, though some remain unidentified and many died during training. When the Red Guardian revealed the motivations behind Phobos's operation, he gave talismans to his two prize pupils, Krylenko and Petrovna, and fled into a radioactive region of Khystym known as the Forbidden Zone.
Upon their graduation from the academy, Krylenko (who adopted the code-name Vanguard) and Petrovna (who called herself Darkstar) began working for the Soviet state as government agents. Darkstar was sent the United States with the Crimson Dynamo and Titanium Man to bring back the former Soviet spy Black Widow, but she rebelled and remained with the Los Angeles-based superteam the Champions until it disbanded. Upon her return to the Soviet Union, she joined her brother Vanguard and the new Crimson Dynamo on a mission to investigate possible alien activities on the Moon, which led to a battle with the American superheroes Iron Man and Jack of Hearts and with the extraterrestrial Rigellians.
A few months later, Vanguard, Darkstar, and the Crimson Dynamo were sent on a mission with Ursus, who had now adopted the code name Ursa Major to eliminate the Presence, who the KGB believed was behind the spread of the radiation of the Forbidden Zone beyond its boundaries. There they battled the Presence, the new Red Guardian (Tania Belinsky) (who had also been turned into a nuclear being) and the Hulk. They soon learned that the Presence was in fact Vanguard and Darkstar's father, and that their former mentor Professor Phobos was behind the expanding radioactive wasteland. After defeating Phobos, his three students decided to sever their ties with the government, which they believed had purposely deceived them. After expelling the Crimson Dynamo (who continued to support the government) from their ranks, they began aiding the people of their country without government authorization.
Eventually the Soviet Super Soldiers were contacted by the director of the KGB, who offered them full amnesty for their unsanctioned activities if they would investigate the disappearance of the Devastator, who had been investigating the Gremlin, a renegade scientist believed hiding in the Forbidden Zone. Though uninterested in serving the state, the team accepted, believing that the Soviet people were in jeopardy. When they arrived in the Forbidden Zone, however, they found that the threat came not from the Gremlin but from the alien race known as the Dire Wraiths, who has built a scientific base in the Zone. With the help of the Gremlin and the Galadorian Spaceknight, Rom, they defeated the Dire Wraiths. In the aftermath, they offered the Gremlin membership in their team, and they made the Wraith citadel their new base of operations. The Gremlin later built a built a suit of armor and became the new Titanium Man, assisting in the investigation of the crash of Magneto's Asteroid M in Russian territory.
After Gremlin's death in battle with Iron Man, the remaining members of the team fled to the United States in search of asylum. They were pursued by a new team of super-powered government agents known as the Supreme Soviets. Using the powers of one of their members, they were able to infiltrate the Avengers base where the Soviet Super-Soldiers had been granted asylum by Captain America and defeated them in battle. Leaving the Soviet Super-Soldiers for dead, the Supreme Soviets teleported away, but the unconscious minds of Ursus, Krylenko, and Petrovna created a "Great Beast" using Darkstar's "Darkforce" power that attacked Moscow. When the Supreme Soviets arrived to battle the threat, they were absorbed by the creature and nearly killed before Captain America convinced the trio to let their enemies live.
Though the three remaining members of the Soviet Super-Soldiers were granted asylum by the United States government, they were later captured by the People's Protectorate, the successor to the Supreme Soviets. Returned to the Soviet Union, they escaped and later joined the underground mutant group known as the Exiles.