McKenzie was drafted in the third round (79th overall) of the 2001 NFL Draft by the New York Jets, and established himself as a premier run blocker over his first four seasons as a professional. McKenzie anchored the right tackle position and helped Curtis Martin achieve three straight 1,000-yard rushing seasons from 2002–2004, including an NFL best 1,697 yards in 2004.
Before the 2005 season, McKenzie joined the New York Giants as a free agent. He suffered a hamstring injury in week 13 of the 2005 season against Giants rival, the Dallas Cowboys. McKenzie made an immediate impact as right tackle for the Giants in the 2005 season, paving the way for Tiki Barber in rushing for a franchise-record of 1,860 yards.
McKenzie was an integral part of the Giants' success in 2007 and won his first Super Bowl ring in Super Bowl XLII. He earned another ring in Super Bowl XLVI despite the lackluster performance of the Giants offensive line that season. McKenzie and the offensive line as a whole played well in the playoffs and the Super Bowl. Following the season, he became a free agent and the Giants announced he would not be re-signed.