When Gaudin made his major league debut, he became the youngest Devil Ray in club history at 20 years and four months and was the 4th youngest player in the majors. He allowed one run in 2.1 innings in his debut on August 1, 2003, against the Kansas City Royals. After posting a very respectable 2–0 record and 3.60 ERA in 15 appearances (including 3 starts) in 2003 for the Devil Rays, he went 1–2 with a 4.85 ERA in 26 appearances (4 starts) in 2004 while splitting time with the Triple-A Durham Bulls.