Conway had dark matches previously with Kurt Angle and Headbanger Mosh, then known as Beaver Cleavage. Conway's TV debut in the World Wrestling Federation (WWF) was on the May 20, 2000, episode of Jakked, where he was defeated by Bull Buchanan. Over the next three years, Conway appeared in tryout matches on Velocity and Sunday Night Heat, losing to wrestlers such as A-Train, Randy Orton, and The Hurricane.
In a match taped for the July 17, 2003 episode of SmackDown!, Rob Conway and Nick Dinsmore appeared under masks as "Los Conquistadores", losing to Rey Mysterio and Billy Kidman. On July 27, at Vengeance, Conway once again competed as the masked Conquistador, this time with Johnny Jeter as his partner, as part of the APA Bar Room Brawl.
Conway made his proper debut for the company on the August 18, 2003, episode of Raw, planted in the audience dressed as an American airman. After Conway was "harassed" by the heel tag team La Résistance (Sylvain Grenier and René Duprée), he was invited into the ring by The Dudley Boyz, who were then feuding with La Résistance. While "celebrating" with the Dudley Boyz and waving the American flag, Conway suddenly hit them both with the flagpole, revealing himself to be a member of La Résistance. The trio feuded with several tag teams, including the Dudley Boyz, Hurricane and Rosey, and Garrison Cade and Mark Jindrak. When Grenier suffered a back injury in October 2003, Dupree and Conway held the group together until the March 15, 2004 edition of Raw when Grenier returned. The trio did not last long after that, however, as Dupree was drafted to SmackDown! on March 22, 2004 during the Draft Lottery.
Grenier and Conway, however, continued to team together as La Résistance on Raw. With American-Franco hostility subsiding, the WWE ceased billing the team as being from France and instead promoted them as being haughty French Canadians who carried the flag of Quebec to the ring, with Grenier often singing the Canadian national anthem. The team held the World Tag Team Championship three times. Their first title reign came when they defeated Chris Benoit and Edge on the May 31, 2004 edition of Raw in Grenier's home town of Montreal, Quebec. Shortly after this Conway grew his hair out and combed it back. The team dropped the belts to the same team of Benoit and Edge at Taboo Tuesday on October 19 when, even though Edge walked out on Benoit, Benoit was able to defeat La Résistance by himself. It was not long before La Résistance reclaimed the tag team gold for the second time on the November 1 edition of Raw, defeating Chris Benoit after Edge walked out on Benoit again. This time La Résistance did not hold the title as long as their last reign; they lost the belts two weeks later on Raw when they faced the team of William Regal and Eugene as well as Tajiri and Rhyno. In a 3-Way Elimination match, they dropped the title to Regal and Eugene. Their third, and final, Tag Team Title reign began at a Raw brand house show on January 16, 2005 in Winnipeg, Manitoba when they defeated Regal and Jonathan Coachman—Regal's actual partner, Eugene, had been injured and Coachman was selected to be his fill in partner, though Regal never tagged him in—to win the belts. La Résistance dropped the belts again a few weeks later on the February 7, edition of Raw, from Tokyo, Japan, to William Regal and his new tag team partner Tajiri. Conway cut his hair back short in March, 2005.
La Résistance repeatedly attempted to regain the gold (mainly on Heat) from Regal and Tajiri in a number of different matches but fell just short each time. During their "last shot" the team thought they had won back the title only to have the decision reversed by referee Mike Chioda due to La Résistance not pinning the legal man. The match was restarted but La Résistance lost the match and their last chance against Regal and Tajiri in a normal tag team contest. The team was given one more chance at Regal and Tajiri, only this time during a Tag Team Turmoil match including five teams—La Résistance, Regal and Tajiri, The Heart Throbs (Romeo Roselli and Antonio Thomas), Simon Dean and Maven, and Rosey and The Hurricane, at Backlash. During the match La Résistance managed to eliminate the champions, but were defeated by the last remaining team (and winners of the match) Hurricane and Rosey.
The team split in mid-May after repeatedly quarreling over his attitude towards men which of them was the superior wrestler. Grenier and Conway went into singles competition with announcers claiming that the members of La Résistance were trying to "one up" each other in singles matches without the other man in their corner. This saw Conway defeat a jobber and Val Venis, while Grenier was defeated by both Venis and Chris Jericho. Both men competed in a triple threat match against Intercontinental Champion Shelton Benjamin for the title; Benjamin won the match not long after the La Résistance members began to argue and fight with each other. This altercation led to a main event match for the June 12 Heat (taped on June 6) in which Rob Conway portrayed the heel, and defeated Grenier. On June 30, 2005, Grenier was a last minute trade in the 2005 WWE Draft, sending him to SmackDown! while Conway stayed on the Raw brand. Conway then began wrestling in singles competition on both Heat and Raw.
On the July 17, 2005 edition of Heat Conway brought back his original identity of Rob Conway, making his new gimmick a narcissistic heel and developing a new appearance (similar to Buff Bagwell) including a biker hat, sunglasses, a mustache, see through tights, and a new haircut. He began referring to himself as "The Con-Man" Rob Conway. During the WWE Homecoming edition of Raw, Conway interrupted a segment involving a number of WWE Legends. After disrespecting the legends, they assaulted him. Conway, seeking retaliation, then went on to have matches against a number of legends, picking up wins over Doink The Clown, Greg Valentine (by disqualification), and Koko B. Ware.
During this time he would go on to begin feuding with Eugene, a big fan of the legends who stuck up for them. At the Taboo Tuesday pay-per-view, Conway teamed with Tomko to face Eugene and a legend (as voted for by the fans). Jimmy Snuka beat out Kamala and Jim Duggan in the voting to become Eugene's partner and picked up the win after a Superfly Splash ending Conway's winning streak. On the next Raw, Conway attempted to take the Intercontinental Championship from Ric Flair, but came up short when he was locked in Flair's figure four leglock.
After losing to Flair, Conway went on a long losing streak, losing almost every match he was in through the rest of the 2005 and the start of 2006. Conway went back to competing on Sunday Night Heat making few appearances on Raw and losing on every occasion. On the April 10, 2006 edition of Raw, Conway debuted a slightly changed look, including longer hair, no mustache, and blonde highlighted hair, in a loss to Rob Van Dam. Conway finally broke his losing streak for one night only on the May 12, 2006 edition of Heat when he won a mixed tag team match with Victoria against the team of Viscera and Torrie Wilson. It was short lived, however, as the next week he was defeated by Jim Duggan, restarting his losing streak but starting a short program with Duggan and his protege Eugene. At the start of August, Conway dropped the Con-Man Gimmick as he stopped wearing sunglasses and his ego dropped. From this point on, Conway was used as a tweener who was desperate to pick up a victory over anyone possible but failed every time he tried.
During the first episode of Raw for January 2007 (1st Jan), Rob threatened to Quit if he lost his match with Jeff Hardy. He did, and was then fired by Vince McMahon.