He began his professional career at ten years old as a member of James Andrews' All-Star Brass and was given his first steady gig by guitarist Danny Barker at The Famous Door on Bourbon Street.

After touring with Marcus Roberts and Elvin Jones in the early 1990s, Payton signed a contract with Verve Records; his first album, From This Moment, appeared in 1995.

In 1996 he performed on the soundtrack of the movie Kansas City, and in 1997 received a Grammy Award (Best Instrumental Solo) for his playing on the album Doc Cheatham & Nicholas Payton.

Besides his recordings under his own name, other significant collaborations include Trey Anastasio, Ray Brown, Ray Charles, Daniel Lanois, Dr. John, Stanley Jordan, Herbie Hancock, Roy Haynes, Zigaboo Modeliste, Marcus Roberts, Jill Scott, Clark Terry, Allen Toussaint, Nancy Wilson, Dr. Michael White, and Joe Henderson.

[5] New Orleans Collective With Wessell Anderson, Christopher Thomas, Peter Martin and Brian Blade SFJAZZ Collective (2004-06) The Blue Note 7 (2008-09) With Eric Alexander With Joanne Brackeen With Bill Charlap With Common With The Headhunters With Joe Henderson With Doc Houlind With Dr. John With Elvin Jones With Abbey Lincoln With Joshua Redman With Yu Sakai [ja] With Jimmy Smith With Allen Toussaint