"I had a chance to hear some great trumpeters like Wendell Brunious, Leroy Jones, Clyde Kerr Jr., and Teddy Riley," Payton said in a 2003 interview, and he also recalled seeing Wynton Marsalis when he was in high school. "I got to hear a bunch of people play trumpet in a town that has been noted for trumpet players since Buddy Bolden. For me, trumpet fit my personality. It suited my voice. You're able to express a wide range of emotions on the instrument," he said.

The turning point for the young Payton came when he was 11, when he heard a Miles Davis quartet album that was in his parents' record collection. With the opening notes of the recording, he knew then he wanted to be a trumpet player and play jazz. He started performing publicly as a ten-year-old and began playing in the streets as a year later. He worked everywhere from jazz funerals to weddings to bar mitzvahs, and played on the streets for tips. Although he knew he wanted to play jazz, he also knew "you can't make a living in New Orleans being a genre-oriented musician." Payton said, "A lot of the guys my father played with in jazz bands were school teachers during the day, and they would play gigs at night and on weekends."

Payton attended New Orleans' high school for the Creative Arts and studied with Clyde Kerr Jr.; he later studied briefly at the University of New Orleans with pianist Ellis Marsalis, who raised Wynton, Branford, Delfeayo, and Jason. Payton learned more from showing up at the elder Marsalis' gigs at Snug Harbor and other Crescent City jazz clubs than he did in the classroom. "He would let me sit in," Payton recalled in 2003, "and the thing with Ellis is he challenges you to be able to teach yourself. That's the key to jazz. Only you can know how you want to sound. A good teacher will facilitate the development of your own style." Payton's college career at UNO was interrupted by the chance to go on the road with drummer Elvin Jones. He had spent time on the road with Marcus Roberts and other touring musicians, but those were shorter stints. Spending two years on the road with drummer Jones was his first big break, he recalled.

Through the years, Payton has recorded and performed with Wynton Marsalis, Dr. Michael White, Christian McBride, Joshua Redman, Roy Hargrove, Doc Cheatham, and Joe Henderson, among others. He began his recording career with Verve Records, and his first album, From This Moment, was released in 1992. Two years later he performed on the soundtrack for the movie Kansas City, and in 1997 he received a Grammy Award for his playing on a collaborative album with then-nonagenarian trumpeter Doc Cheatham, Doc Cheatham & Nicholas Payton. He also released 1995's Gumbo Nouveau, 1997's Fingerpainting: The Music of Herbie Hancock, 1998's Payton's Place, 1999's Nick@Night, and 2001's Dear Louis.

Payton signed with Warner Bros. in 2003, releasing the '70s fusion-influenced Sonic Trance. An auto accident briefly sidelined Payton's career as he took time to fully recover. He returned with Mysterious Shorter on Chesky in 2006 and Into the Blue on Nonesuch in 2008. Well known as a risk taker, Payton took one of his grandest on 2011's Bitches. A concept recording that details the stages and ending of a romantic relationship, Payton composed and arranged all 16 songs (which include lyrics), played every instrument, sang and played trumpet throughout, and produced the entire set. He is accompanied on the album by special guest vocalists Cassandra Wilson, Esperanza Spalding, N'Dambi, Chinah Blac, and Saunders Sermons.