Hickenbottom began to train under Mexican professional wrestler Jose Lothario. During his training, Hickenbottom adopted the ring name, Shawn Michaels. After his training with Lothario, he debuted as Shawn Michaels with Mid-South Wrestling and Texas All-Star Wrestling (TAW) promotions in 1984. During his time with TAW, Michaels and Paul Diamond were awarded the TAW Tag Team Championship by Chavo Guerrero, Sr. He also worked for Central States Wrestling. There, he and tag team partner Marty Jannetty defeated The Batten Twins for the Central States Tag Team Championship, later losing it back to the Battens. Michaels also made several appearances in the Dallas, Texas-based World Class Championship Wrestling throughout 1985.

Michaels made his national-level debut at the age of twenty in American Wrestling Association (AWA), once again teaming with Marty Jannetty. The pair were billed as "The Midnight Rockers" and held the AWA World Tag Team Championship, defeating Doug Somers and Buddy Rose. In 1987, The Rockers were signed by a competing promotion: the World Wrestling Federation (WWF).They were fired from WWF two weeks later, for a bar incident (a misunderstanding, according to Michaels' autobiography). They then returned to AWA, but were re-signed by WWF a year later.