Williams and Miller debuted with the WWF in the midst of its aggressive national expansion, giving them greater exposure than they had ever had before. The team's name was changed to The Bushwhackers, and they changed their violent style to a comedic style which was an instant hit with WWF fans. The comedy act involved licking (each other as well as their opponents), exaggerated arm movements, and more. The Bushwhackers made their WWF in-ring debut on 3 January 1989 at a WWF Superstars of Wrestling taping.
Only a few days into their run with the WWF, the Bushwhackers had their first match with a team they would encounter repeatedly over the next year and a half, The Bolsheviks (Boris Zhukov & Nikolai Volkoff). In February the Bushwhackers began a feud with The Fabulous Rougeau Brothers, the first feud to really feature the Bushwhackers on WWF television. The two teams would take their conflict to WrestleMania V which saw the Bushwhackers victorious in their WWF Pay Per View debut as a team. The WrestleMania match was not the end of the Bushwhackers/Rougeau feud as the teams clashed again on the 14 October edition of Saturday Night's Main Event (taped 21 September), once again the Bushwhackers were victorious. The Bushwhackers and the Rougeaus would clash twice more, first at the 1989 Survivor Series and again at the 1990 Royal Rumble both times with the Bushwhackers getting the best of the Rougeau brothers.
During this time the Bushwhackers began to feature in a long series of comedic vignettes, usually subjecting ”Mean” Gene Okerlund to their wild and wacky ways (and sardine eating antics). These vignettes were often featured on Coliseum Home Video releases where they served as the “link” between matches.
The Bushwhackers quickly became one of the most popular duos among the viewers, chiefly due to the wildly comedic nature of their antics (including their trademark "Bushwhacker Walk"), their catchy faux-Australian musical theme, and the high level of their friendly interaction with the audience. By 1990 the Bushwhackers were established as a solid mid-card comedy act feuding with the newly establish heel team known as Rhythm and Blues (The Honky Tonk Man and Greg Valentine). The Bushwhackers’ WrestleMania VI appearance came at the expense of Rhythm and Blues as they showed up during a segment, attacked Honky Tonk Man and Valentine and then broke R & B’s guitars to the delight of the crowd. Later on the team would be used to help establish newcomers The Orient Express (Pat Tanaka and Akio Sato). The feud with the Orient Express culminated at Survivor Series 1990 where Williams and Miller teamed up with Nikolai Volkoff and Tito Santana to form “The Alliance” and take on Sgt. Slaughter, Boris Zhukov and the Orient Express team dubbed “The Mercenaries”. The Bushwhackers eliminated the Orient Express but were eliminated themselves as well.