Hart brought along with him Kendo Nagasaki, renamed the Dragon Master, and the Great Muta. Like Nagasaki used to, Muta sported face paint and would spew mist into the air before and even during his matches. It wasn’t long before Muta and the NWA’s most popular grappler, Sting crossed paths. Sting was the reigning NWA World Television Champion and was quickly targeted by Muta, thus beginning one of the greatest feuds in wrestling history, spanning over a decade. This was the first major feud for both of the young, up and coming stars and both men gave it their all in every encounter. Their first major encounter occurred at the Great American Bash on July 23, 1989. The undefeated Muta was challenging Sting for his Television Title; unfortunately neither competitor arose victorious as both men’s shoulders were counted down, forcing the match to be declared a "no contest" and the title held up. The subsequent rematch took place on September 3, 1989 to determine the rightful holder of the Television Title. Muta bested Sting in this classic rematch to wear the NWA TV title, his first championship gold in over two years.

While Muta took on all challengers for his title, his feud with Sting continued on hotter than ever. These two met in singles and tag matches all over the country, with Muta emerging victorious in nearly every encounter. Sting was able to gain a measure of revenge against Muta at Halloween Havoc on October 29, 1989, as Sting and Ric Flair defeated the team of Terry Funk and the Great Muta in a thrilling cage match. Enraged that his partner cost his team the match, Muta violently attacked Funk until Sting and Flair made the save. Muta continued defending the TV Title successfully and rode his undefeated streak into the NWA’s biggest event of the year, Starrcade ‘89. The format for Starrcade was an Iron Man Tournament; Ric Flair, Lex Luger, The Great Muta and Sting would all compete against one another in individual matches and the man with the most points at the end of the show would be winner and subsequent number one contender to Flair’s World Heavyweight Title. If Flair won, none of these men would be in line for his next title defense. Hopes were high that Muta would emerge as the number one contender to finally get a shot at Flair, but unfortunately Muta was not at his best that evening. In his first match of the evening, Muta’s year long undefeated streak came to an end as Ric Flair won their match via pinfall. Muta’s long time foe Sting was his next opponent. Every match between these two were classics, this one was no exception. Sting was able to escape Muta’s moonsault to finally score a pinfall victory over his archrival. Muta’s hopes of winning the tournament were gone, but he had one last shot at redemption. His final match of the tournament was against Lex Luger. As Luger attempted to put Muta into the "Torture Rack" Muta sprayed his mist into Luger’s eyes, getting himself disqualified. Sting would go on to win the tournament and align himself with Ric Flair, Arn and Ole Anderson, thus reforming the Four Horsemen. Although Muta’s performance in the tournament was disappointing and his undefeated streak was over, he still had his Television Title, but not for long. Arn Anderson challenged and defeated Muta for the Television Title, with a little help from Sting and Ole Anderson, on January 20, 1990. Muta left the NWA shortly thereafter.

Although his tenure with the NWA ended on a bad note, he returned to his homeland a hero, ready to conquer Japan just as he did America. Upon returning to Japan, it didn’t take Mutoh long to capture championship gold again. He and Masahiro Chono defeated the team of Masa Saito and Shinya Hashimoto on April 27, 1990 to become the IWGP World Tag Team Champions. They would hold the titles for seven months before getting dethroned by Hiroshi Hase and Kensuke Sasaki. Mutoh and Hase would have several blood baths with one another in Japan, with Mutoh usually emerging victorious. After briefly settling their feud, they teamed up with one another to win the IWGP Tag Titles from Rick Steiner and Scott Norton, who was subbing for Scott Steiner. During their reign, Mutoh won the biggest match of his career, defeating Riki Choshu on January 4, 1992 to become the IWGP World Heavyweight Champion. This victory established Mutoh as a singles star in Japan. Mutoh briefly defended both the IWGP Heavyweight Title and the IWGP Tag Team Titles, but he and Hase eventually ran into the monster team of Big Van Vader and Bam Bam Bigelow, leaving Mutoh to concentrate on his singles title. During his reign, Mutoh wrestled his old rival from the US, Sting on several occasions, reviving their old feud. After a few encounters, they put their differences aside and teamed together against the Steiner Brothers in arguably some of the greatest tag team matches ever. Mutoh would next accomplish a task no other wrestler before or after him has been able to do.

Mutoh defeated the reigning NWA World Heavyweight Champion, Masahiro Chono, on January 4, 1993 at the WCW/New Japan Super Show III in Tokyo, Japan to unify the IWGP and NWA World Titles. Mutoh was now holding one of Japan’s and America’s most prominent and prestigious titles simultaneously. Muta would drop the NWA Title to Barry Windham within a month in Ashville, North Carolina at Super Brawl III. Mutoh continued defending the IWGP title throughout 1993 until Shinya Hashimoto was able to take the title from him in September. Mutoh would go over a year before becoming champion again. The re-formed team of Mutoh and Hiroshi Hase defeated the Hell Raisers, Road Warrior Hawk and Kensuke Sasaki, to become IWGP Tag Team Champions on November 11, 1994. Their reign lasted half a year until history repeated itself. Mutoh became a two time IWGP World Champion by defeating Shinya Hashimoto on May 3, 1995. Intelligently, Mutoh and Hase vacated the Tag Team belts so Mutoh could concentrate on defending his newly won World championship. Mutoh was able to unify the IWGP and UWIF world titles by defeating Nobuhiko Takada in May of 95. Takada eventually got revenge and won the unified titles on January 4, 1996. A knee injury slowed Mutoh down for a while, but upon his return he and Masahiro Chono formed the Japanese version of the N.W.O. and defeated the team of Kensuke Sasaki and Kazuo Yamazaki to once again become the IWGP Tag Team Champions. This marked the second time this duo had captured the tag titles and fifth time for Mutoh. Unfortunately, their seventh month reign ended on May 7, 1998 when Mutoh had to undergo knee surgery. After returning from successful knee surgery, Mutoh captured the IWGP World title once again by defeating Scott Norton on January 4, 1999. He would hold the title for nearly a year before being upset by Japanese legend Genichiro Tenryo in December.

In 2000 New Japan came up with a way to send Muta back for a brief run in the United States. The angle was that of WCW stealing Muta away from New Japan for six months, WCW realizing Muta’s drawing potential jumped at the opportunity. This would mark Muta’s longest stint in the States since 1989. Muta appeared briefly in 1991 at the Clash of the Champions in a televised loss to Lex Luger and wrestled on a few Monday Nitro’s in 1997. Muta made an immediate impact upon his arrival in WCW. He competed in and advanced deep in a tournament to crown a new United States Champion. Muta would soon form a team with WCW star Vampiro and they quickly won the WCW Tag Team Titles from Kronik at New Blood Rising on August 13, 2000. This was a very significant moment in Muta’s career, as he can now lay claim to holding both the singles and tag team world heavyweight titles in Japan and America. Rey Misterio Jr and Juventud Guerra dethroned Muta and Vampiro the following night, thanks to interference by Muta’s long time rival-Sting. Sting and Muta’s rivalry was renewed, but failed to recapture the magic of their earlier encounters. They only met two times with any significance, with Muta getting a win on Nitro, and Sting picking up the victory at Fall Brawl 2000. Soon thereafter, Muta left WCW and returned to Japan.