On the surface, country music legend Willie Nelson and jazz trumpet icon Wynton Marsalis might seem like an unlikely combination. But when the two came together in January 2007 to perform live at Lincoln Center, they discovered a connection far beyond their admiration for each other's music. Finding common ground and a mutual love of jazz standards and the blues, they later turned the performances into the newly released album Two Men with the Blues.

All Things Considered host Andrea Seabrook spoke to the two musicians about their first-ever collaboration as the two sat on Nelson's tour bus before an appearance on The Tonight Show.

Common Ground In The Blues

Nelson says that music hasn't changed much in his lifetime.

"It's all music," Nelson says. "You got so many notes and there's so many words to throw in there, and you get different people mixing it up different ways. But you put it all together, and that's music."

Marsalis adds that the common ground between them makes playing together a natural fit.

"We're all part of the same root," Marsalis says. "It's like eating barbecue: Texas people barbecue; Louisiana people barbecue catfish. We taught them what to do with a catfish. We don't have to come together to do that, you know?

"All American root music is the same: We play shuffle rhythms, we play the blues, we have songs that we know. It was no strain for us, or to play with each other's songs on the album — all songs that I grew up hearing, of course. Willie is a part of that whole history."

"Its kinda like gettin' together more than coming together for the first time," Nelson adds. "We've always played basically the same."

'Talking's Not Necessary'

When the two rehearsed for the first time in preparation for the concerts in The Allen Room at Jazz at Lincoln Center, Marsalis realized that those connections to the music allowed them to communicate ideas without speaking a word.

"The first thing about him is his phrasing," Marsalis says. "His phrasing is very unpredictable, but it comes out poetic and very logical, and his sense of harmonies [is] very sophisticated. But he's unassuming."

"We had one moment in a song," Marsalis continues, "where we were playing the ending wrong. Willie turned around and he just looked at the rhythm section and he didn't say anything. No words were spoken. We played it again and it still wasn't right, and then Willie looked at them. We played it a third time, it was right, and when they finished playing, he looked at them and said, 'Mighty fine, gentlemen.' "

"The talking's not necessary," Nelson adds.

Marsalis says he was able to learn from those understated moments.

"Willie has been on the road for so long, and he's contributed so much," Marsalis says. "If you walk with him on the street and you see the way people love him, his integrity and who he is, he's so much himself. I'm not even going to talk about musical things. I'm just gonna talk about just as a man — he's very relaxed. He doesn't over-rehearse stuff: When its good enough to be played, he stops; he's fine with it.

"He also has an incredible work ethic," Marsalis adds. "He doesn't complain about anything; he's serious about what he's doing; he's professional; he gets to his job. He's a man of deep integrity, so he's strengthened my own integrity and my understanding of how to relax when dealing with other people."

Nelson says he found many things to learn from Marsalis, too.

"Every song we play," Nelson says, "I take something away. And these incredible memories I'm building playing with these guys and with Wynton, they're all teachers. You can't be around them without learning. You hear it, and you go away thinking about it."

Copyright 2022 NPR. To see more, visit https://www.npr.org.