He began wrestling in the World Wide Wrestling Federation (WWWF) (currently known as WWE). Wrestling as Bepo Mongol, managed by "Captain" Lou Albano and partnered with Geto Mongol, he captured the WWF International Tag Team Titles from Tony Marino and Victor Rivera on June 15, 1970. After losing the titles to Luke Graham and Tarzan Tyler in a match that unified the WWF International and WWF World Tag Team Titles, Mongol went on to singles competition under the name Nikolai Volkoff.
In 1974, Volkoff appeared in a memorable match at a sold out Madison Square Garden and wrestled one of the sport's most famous champions, the great Bruno Sammartino. Volkoff chased the WWF title for the majority of his early career and was always given a considerable number of title shots from whoever was the current WWF Champion.
In 1984, Volkoff returned to the now WWF and teamed with the Iron Sheik. It was at this point that Volkoff really pushed the envelope and began to sing the national anthem of the Soviet Union before every match, in order to gain even more heat for being a foreign heel.
The new team of Volkoff and The Iron Sheik captured the coveted WWF Tag Team Championship from The U.S. Express (Mike Rotundo and Barry Windham) at WrestleMania, on March 31, 1985. After losing the titles back to Rotundo and Windham three months later, Volkoff began to wrestle more in singles competition, picking up a notable feud with Corporal Kirchner. They faced off in a flag match at WrestleMania 2, which Kirchner won. Volkoff also wrestled Hulk Hogan for the WWF World Heavyweight Championship on several occasions in 1985 and 1986, but did not win.
In the fall of 1986, Volkoff's manager Classy Freddy Blassie sold half interest in his stable of superstars to the “Doctor of Style,” Slick. Giving Slick co-managerial rights to Nikolai Volkoff, Classy Freddy Blassie also shared the contracts of the Iron Sheik and Hercules. Blassie eventually retired in the fall of 1986. Sheik and Volkoff feuded with WWF newcomer Jim Duggan for the majority of 1987.
In late 1987, Volkoff was teamed with Boris Zukhov, to form The Bolsheviks. However, this tag team combination for Volkoff did not gain the success as did his partnership with The Iron Sheik. As they lost the public eye due to many losses, they eventually lost their manager Slick. The Bolsheviks never held any titles together, and are perhaps best remembered for being defeated in 19 seconds by The Hart Foundation at WrestleMania VI. Eventually, by 1990, The Bolsheviks split up. Volkoff publicly ended the partnership prior to a match where he confronted Zukhov and then started singing "The Star-Spangled Banner", drawing loud cheers from the audience and turning face in the process.
A short time after The Bolsheviks split, Volkoff became a fan favorite for the first time in his career. His gimmick was now that of a recently liberated Lithuanian, following the fall of the Soviet Union; he became very pro-west which led to a feud with Sgt. Slaughter who was involved in an Iraqi sympathizer role and teamed with the Iron Sheik, who had recently began an Iraqi gimmick. After Volkoff's team defeated Slaughter's team at the 1990 Survivor Series (Tito Santana being the sole survivor), Volkoff left the WWF at the end of 1990. He would make a brief return to compete in the 1992 Royal Rumble match.
In 1994, Volkoff again returned to the WWF and became a sympathetic heel by playing the whipping-boy of Ted DiBiase's Million Dollar Corporation. Volkoff had kayfabe fallen on hard times and was forced to take a job working for DiBiase and his new Corporation. As low man in the group he was forced to wrestle matches no one else wanted to or sent out to "soften up" opponents for other members of the stable as the sacrificial lamb of the group. The disrespect even extended to renaming him "Nickel & Dime" Volkoff and DiBiase forcing him to place a ¢ on his trunks where the Russian sickle once was along with a sign on his ring attire that read "Property Of The Million Dollar Man". Following this last run in the WWF, Volkoff entered a semi-retirement.
Volkoff made a brief cameo on an episode of Shotgun Saturday Night where Todd Pettengill discovered him homeless sleeping in a box on the streets of New York. He also appeared at WrestleMania X-Seven in the Gimmick Battle Royal.
On February 3, 2005, Volkoff was announced as one of the WWE Hall of Fame inductees for the Class of 2005. He was inducted on April 2, 2005 by Jim Ross in the Universal Amphitheatre in Los Angeles, California.
Volkoff made his first appearance on WWE television in over 2 years on the August 13, 2007 edition of Raw as a contestant on WWE Idol. Volkoff appeared alongside the Iron Sheik and Howard Finkel, although Volkoff was the only one who sang. Volkoff sang the Soviet Union national anthem, receiving boos from the crowd (despite being a face) and was insulted by judge William Regal, although judges Mick Foley and Maria both praised the performance. In response, Sheik, who was also insulted, went on a tirade until both he and Volkoff were escorted out of the building by security.
The March 10, 2008 edition of WWE Raw, featured rematches from previous WrestleManias. The Iron Sheik appeared along with Nikolai Volkoff to face off against the U.S. Express in a rematch from the first WrestleMania. The match was cut short however by Jillian Hall, who came out to sing "Born in the U.S.A."
On the November 15, 2010, edition of Raw, as part of the Old School theme, Volkoff appeared with the Iron Sheik, singing the Soviet national anthem before being interrupted by Santino Marella and Vladimir Kozlov, the latter of whom then sung a duet with Volkoff of the Russian National anthem.