Johnson made his WWF debut as a face on the October 23, 1995 episode of Raw. Prior to his first televised match, he appeared at the end of a Raw taping by entering a post-match brawl and slamming Yokozuna. He made his pay-per-view debut at Survivor Series, as the team of Razor Ramon, Yokozuna, Owen Hart, and Dean Douglas took on the team of Johnson, Shawn Michaels, Sycho Sid, and The British Bulldog. In the end, Johnson, Michaels, and Bulldog won the match as the survivors of their team. At Season's Beatings on December 17, Johnson defeated Buddy Landel (who replaced Dean Douglas) in only 42 seconds. After the match, Johnson was interviewed by Jerry Lawler, at which time Lawler distracted him in order for Jeff Jarrett to attack him, starting a feud between the two in the process. At the 1996 Royal Rumble, Johnson defeated Jarrett by disqualification after Jarrett struck him with a guitar (Ahmed got taken to the Hospital because of a concussion from the guitar). At WrestleMania XII, Camp Cornette (Vader, Owen Hart, and The British Bulldog) took on the team of Yokozuna, Jake "The Snake" Roberts, and Ahmed Johnson. Camp Cornette won when Vader pinned Roberts with the Vader Bomb. At Good Friends, Better Enemies on April 28, Roberts and Ahmed teamed up to take on Hart and Bulldog. While Jim Cornette had the referee distracted, Bulldog hit him in the knee with Cornette's tennis racket; he then forced Roberts to submit with a single leg Boston crab. After the match, Roberts and Ahmed attempted to put Roberts' python, Revelations, on Cornette, but Hart pulled Cornette out of the ring.
At King of the Ring, Johnson defeated Goldust to win the Intercontinental Championship. As the first African American Intercontinental Champion, most assumed it was only a matter of time before he climbed to main event status. He was soon paired on-screen with Shawn Michaels in several tag team matches and often helped Michaels against Jim Cornette and his men, known as Camp Cornette. At International Incident, Johnson along with Sycho Sid and Michaels lost to Vader, Owen Hart, and the British Bulldog.
On the July 22 edition of Raw, Michaels and Johnson teamed again and challenged The Smoking Gunns (Billy and Bart) for the Tag Team Championship. During the match, Faarooq Asad debuted and attacked Johnson. This was supposed to lead to a match at SummerSlam for the Intercontinental Title. On the August 5 edition of Raw, Ahmed won an 11-man battle royal, last eliminating the man whom he beat for the IC title, Goldust to be the #1 contender for the WWF Championship for the day after SummerSlam. However, Johnson was diagnosed with legitimate kidney problems, and was forced to miss SummerSlam, and his scheduled WWF Championship match the following night. As a result, he was out for four months and in order to keep the angle going, the attack by Farooq was said to be the cause of the kidney damage. By the time the news was made public on WWF programming and it included the 11-man battle royal which Johnson won. Voice-over correction was done so that Ahmed's participation in the battle royal was said to be against doctors' orders when in reality his kidney problem had yet to be discovered. The injury forced him to vacate the Intercontinental Championship, which was subsequently won in a tournament by Marc Mero. The title shot the day after Summerslam was given to the runner-up of the battle royal after Goldust had won a mini battle royal involving the final four participants eliminated in the battle royal won by Ahmed Johnson.
He returned in 1996 to enter a feud with Faarooq (who by then had a new gimmick and formed his own stable, the Nation of Domination). Finally, the two had an encounter at Royal Rumble 1997, where Johnson won by disqualification. Two days later, Johnson and The Undertaker defeated Faarooq and Nation member Crush in a No Holds Barred match at the Triple Threat event. He began teaming with the Legion of Doom (Hawk and Animal) and the three fought the entire Nation at WrestleMania 13 in a Chicago Street Fight. At A Cold Day In Hell, he defeated Crush and Savio Vega in a gauntlet match before losing to Faarooq.
Johnson eventually in June 1997, turning on WWF Champion The Undertaker and joined the New Nation, with Kama Mustafa, D'Lo Brown, and Faarooq. Johnson was injured soon after this; he was scheduled to face Undertaker at Canadian Stampede for the WWF Title, but was plagued by injuries and was replaced by Vader.
The Nation turned on him after he recovered and returned in August 1997, which resulted in Johnson turning face once more. He restarted his feud with the Nation, and would reunite with the Legion of Doom as well as join forces with Ken Shamrock during the feud. At Survivor Series 1997, they defeated the Nation in a Survivor Series match. His last WWF appearance was at the pay-per-view No Way Out of Texas in February 1998, alongside Shamrock and the Disciples of Apocalypse (Chainz, Skull, and 8-Ball) against the Nation.