Ellis stayed in New Orleans, and the musical hotbed had a big impact. "I probably learned more there about playing jazz in those three years than I had. It was the beginning of my focus on playing jazz, and I mostly learned from playing it, listening and sitting in. It was a great window of opportunity. Nicholas Payton hadn't signed with Verve and was always around and always playing. He was enormously influential on all the young guys. It was really cheap to live and lots of informal gigs. I haven't seen anything that exists like that. It doesn't even exist like that there anymore. I haven't seen anything like it; a small community of people where everybody is hungry and there's a lot of chances to play. We had three or four weekly gigs where we just played jazz, just played tunes.
"When I was in New Orleans and we were playing jazz, very straight ahead music, I was obsessed with Dexter Gordon, Sonny Rollins, Charlie Parker. I even got heavily interested in Lester Young, Coleman Hawkins, Ben Webster. I got consumed by John Coltrane, as so many saxophone players do. I still think listening to Coltrane is dangerous for me. I think for lots of people it sounds so strong it pulls you in. It's like a tractor beam. All of a sudden your whole musical universe is defined by John Coltrane. You can hear that in people who came closer to him in age."
While in New Orleans Ellis was playing in the French Quarter when he had a strange encounter with a patron that led on one of several odysseys overseas. "This guy from Singapore during the gig flipped me a business card. I didn't even speak with him. It said, 'Call me up at the Sheraton. Here's my number if you're interested in coming to Singapore and playing with my band.' I was 18 or 19. I never even heard of Singapore, but I called him and spoke with him. He knew, and had played with people that I knew, so it didn't seem like such a random thing. A trumpet player named Leroy Jones had been out there. He had a record with, like, [drummer] Al Foster. I researched him a little bit and realized he was legitimate. I took the risk and went out there."
What was supposed to be six months to a year ended after three months when the club where he was playing in the house band failed. "But it was perfect for me, because I was about at the end of my time that I really wanted to be there," he adds.
Soon after returning to New Orleans, he traveled to Germany with Walter Payton, a bassist and father of Nicholas Payton. Ellis was got involved in the inaugural year of the Jazz Ambassadors program, run through the State Department. "We went o seven countries in African playing jazz duo, me and a guitarist. It was kind of crazy."
After returning to New Orleans, he was chosen as a semi-finalists in the 1996 Thelonious Monk International Saxophone Competition, with judges included Wayne Shorter, Jackie McLean, Jimmy Heath, Joe Lovano, and Joshua Redman. He tried New York City for a time, and returned to school. He finished studies at the New School for Social Research / Mannes Jazz between 1997 and 1999. All the while, he continued to freelance, record and work on his own music.
Then it was back to the Crescent City, where Ellis continued playing jazz in various groups including Jason Marsalis' quintet, among other work. When the school year ended, Ellis was gone, headed back to New York. All this work and experience was leading him down the road to recognition and career advancement, though Ellis, in his calm fashion, is hard pressed to think of it that way.
"When I was young, one of the first things that happened was when I went to the University of New Orleans I ended up meeting and studying some with Ellis Marsalis. The first tour I ever did was a little three-day tour when his record came out, Whistle Stop. That was a confidence boost. I started to fell like, 'wow, I might actually be able to do this.'" But, adds Ellis, "I'm not sure if I've ever had any big break. When I was in New Orleans I played with everyone and it never really had that kind of upward mobility feeling to me so much. I wasn't even thinking about that so much. I was trying to figure out chord changes and stuff. Unquestionably the biggest break, for lack of a better way of talking about it, I guess, was when I got the gig with Charlie Hunter. That was in 2000."