Tyler began wrestling for NWA Mid-America during the late 1970s eventually being chosen by NWA Mid-America Tag Team Champion Gypsy Joe in February 1978 to replace Dutch Mantell who had previously forfeited his half of the title. After losing the titles to George Gulas & Tojo Yamamoto two months later, he would compete for NWA Central States and later wrestled Dewey Robertson in tag team matches with Matt Borne as well as several 6-man tag team matches against Kerry Brown & Tommy Sharp and faced Dick the Bruiser in an interpromotional event between the NWA and the WWF on November 7, 1980. He later lost to Terry Taylor in a match for the vacant NWA Central States Television Championship in January 1981 shortly before winning the promotion's heavyweight championship from "Bulldog" Bob Brown on April 1. After three months, Tyler lost the title to Bob Sweetan on July 23, 1981. Teaming with J.J. Dillon several weeks later, he and Dillon would defeat Bob Sweetan & Terry Gibbs for the NWA Central States Tag Team Titles on August 27, although they were forced to vacate within two months. The following month, he faced Terry Gibbs and Bob Sweetan in singles matches and later lost to Sweetan and Bob Brown in a tag team match with Gene Lewis on September 20, 1981. He also teamed with Steve Sybert in the NWA North American Tag Team Championship Tournament and was eliminated in the opening rounds by Dusty Rhodes & Bugsy McGraw in late 1981. Facing NWA World Heavyweight Champion"Nature Boy" Ric Flair in several matches during 1982, he later began teaming with Bob Brown defeating Dewey Robertson and Hercules Hernandez for the Tag Team titles on September 20, 1982. Although losing the titles to Yasu Fuji & Kim Duk on March 3, he and Brown would regain the titles in a championship tournament on May 26. He and Brown also won the NWA International Tag Team Championship from Timothy Flowers & Terry Adonis in Vancouver, British Columbia on May 30, 1983. Eliminated by Jerry Blackwell during the opening rounds of the NWA Missouri Heavyweight Championship Tournament on July 15, he and Brown would feud with The Sheiks over the tag team titles throughout the year before Brown was injured by 666 during a match in December 1983 and forced to vacate the titles. Regaining the title from Super Destroyer on October 20, he would later over the title with Tully Blanchard, "Crazy" Luke Graham and Ted Oates before losing the title to Hacksaw Higgins on October 6, 1983. During his last year in the promotion, he and Luke Graham especially would face each other in a series of steel cage matches eventually losing to Graham in Kansas City, Missouri on May 10, 1984. He would later defeat former tag team partner Gypsy Joe for the NWA Central States Television title on September 22, 1984 before losing the title a month later to Marty Jannetty.
Moving on to the Mid-Atlantic territory, Tyler had a brief yet violent feud with Wahoo McDaniel before siding with The Assassin in his feud with Paul Jones' Army later teaming with The Assassin at Starrcade '84 to defeat The Zambuie Express with manager Paul Jones in an Elimination Tag Team match on November 2, 1984. With The Assassin and Charlie Brown, he would defeat Superstar Billy Graham, J.J. Dillon and Paul Jones in a 6-man tag team match on January 6 and later faced Graham in both tag team and 6-man tag team matches later that month. Defeating Ron Bass for the NWA Mid-Atlantic Heavyweight Championship on March 16, he was scheduled to defend his title on Jim Crockett's Championship Wrestling from Georgia in its first episode since Black Saturday, however, the main event was canceled after an accident caused the middle ring rope to snap during a match between Black Bart and Ron Rossi on April 6, 1985. Months later, he would team with "Ragin' Bull" Manny Fernandez and Sam Houston to defeat Abdullah the Butcher, The Barbarian and Superstar Billy Graham at The Great American Bash '85 on July 6 and later teamed with Fernandez and Houston to defeat Ivan Koloff's The Russian Team for the NWA Mid-Atlantic Six-Man Tag Team Championship in July 1985 and successfully defended the titles against before losing the titles back to Russian Team later that year. He would later forfeit the NWA Mid-Atlantic Heavyweight Championship after leaving the promotion in July 1985, however he refused to return the title claiming then booker Dusty Rhodes withheld money owed to him, and a third version of the belt was eventually used.
