Historia tag teamu Nikolai Volkoff i Boris Zhukov jeszcze przed stworzeniem tag teamu odgrywali role heelów i rosyjskich komunistów. Volkoff do 1987 roku był w tag teamie z The Iron Sheikiem w WWF, a Boris Zhukov walczył w organizacji American Wrestling Association. Jednak po tym jak Sheik został zwolniony, WWF postanowiło zatrudnić Zhukova by został nowym partnerem Volkoffa. The Bolsheviks zaczynali jako silny zespół, pokonując w ciągu pierwszych kilku miesięcy The Young Stallions (Jim Powers i Paul Roma) i The Rougeau Brothers (Jacques Rougeau i Raymond Rougeau).
Pierwszym pay-per-view duetu było Survivor Series. The Bolsheviks wzięli udział w pojedynku dziesięciu tag teamów. Odpadli jako pierwsi w drugiej minucie po tym jak Tito Santana z zespołu Strike Force przypiął Zhukova. Obaj wzięli też udział w battle royalu na WrestleManii IV. Zhukov wyeliminował Hillbilly Jima, ale później razem z partnerem sam został wyeliminowany przez Kena Paterę, który przy okazji wyeliminował też samego siebie.