After leaving the UFC, Frye went into professional wrestling and was trained by Brad Rheingans and Curt Hennig. He debuted for New Japan Pro-Wrestling (NJPW) in August 1997, defeating Kazuyuki Fujita in his first match. By 1998, Frye began to rise in the ranks as he quickly became one of the company's lead heels. On April 4, 1998, Frye won the Antonio Final Opponent tournament and earned the right to wrestle NJPW founder and wrestling legend Antonio Inoki in his retirement match, which took place later that night. Frye lost that fight. After a brief feud with Kensuke Sasaki at the end of that year, Frye joined Masahiro Chono's new stable, Team 2000, in early 1999. After joining, Frye would spend most of 1999 and early 2000 feuding with Scott Norton over the unofficial title of Gaijin Ace, took part in the G1 Tag League in 1999 with Chono, and make two challenges for the IWGP Heavyweight Championship but was unsuccessful in each attempt. He lost out to Keiji Mutoh in his first title shot in April 1999 and was defeated by Kensuke Sasaki in his second in February 2000.