Mendoza made his major league debut in 1996, going 4-5 with a 6.79 ERA in his rookie season. He did not appear on the postseason roster. In 1997, Mendoza went 8-6 with a 4.24 ERA, while starting 15 games, as both a starter and a reliever. He also appeared in his first two postseason games in 1997, going 1-1 with an ERA of 2.45 while throwing 133 and 2/3 innings, a sharp increase from the 53 he pitched in 1996.
The following year, Mendoza struggled to a 9-9 record with an ERA of 4.29 in 123 2/3 innings pitched. That year, he started only six games and was quickly moved to the bullpen. He gave up 68 runs that year, a career worst, and was left off of the roster for the 1999 American League Division Series. He rejoined the team for the Championship Series, where he pitched 2 1/3 innings and pickup up a save. In the World Series, he pitched 1 2/3 innings of relief and surrendered 3 hits and 2 runs, all earned, however, he still earned the win as the Yankees went on to sweep the Braves 4-0.
Mendoza's performance improved slightly in 2000 as he went 7-4 with a 4.25 ERA in 65 and 2/3 innings pitched, including his first complete game since 1998, and last of his career. Despite his improved performance, he was left off of the postseason roster. The following year, he was 8-4 with a 3.75 ERA, and returned to the postseason. In the 2001 American League Division Series, he pitched in relief during three games and allowed only two hits with no runs allowed. In the Championship Series, he appeared in relief during three games and allowed one home run, (his only earned run in that series), pitching 5 1/3 innings to a 1.69 ERA. In the 2001 World Series, he pitched 2 and 2/3 innings of 1-hit ball as the Yankees fell to the Diamondbacks in seven games. In 2002, Mendoza pitched in 62 games to an identical 8-4 record with a slightly better ERA of 3.44. He pitched 1 and 1/3 innings in the 2002 American League Division Series against the Angels, surrendering only two earned runs as the Yankees were defeated three games to one. On October 28, 2002 he was released by the Yankees.
On July 24, 2004, Mendoza pitched two hitless innings to pick up the win against his former team, the Yankees. The Red Sox were trailing 9–4, before winning 11–10.
After recovering from shoulder surgery during the 2005 offseason, Mendoza returned to the Yankees after September 2005 callups, becoming one of three members of the 2004 Red Sox to play for the 2005 Yankees, along with Mark Bellhorn and Alan Embree. After the 2005 season, Mendoza signed a minor league contract with the Yankees.