“I wasn’t thinking of it like, ‘Oh, my god. We are about to celebrate our 20th anniversary. What are we going to do?’” recalls Warren Haynes this past July from Cologne, Germany during Gov’t Mule’s short but sweet nine-date European tour. “It was just what happened.”

The singer/guitarist/jamband ambassador is referring to the band’s new album Shout!—to be released on September 24, it’s the group’s 12th full-length record following 2009’s By A Thread and Haynes’ 2011 solo effort, Man In Motion. Haynes is as surprised as anyone to be celebrating such a landmark anniversary.

“Everything we’ve accomplished has been done organically because we started the whole concept as a temporary one,” he says of the group’s founding in 1994 as an outlet from playing in The Allman Brothers Band, which he had joined full-time five years earlier. “We didn’t have any vision of this thing going [for] a year, two years, five years or 10 years. We were having fun, seeing what happened and not putting any pressure on ourselves.”

One could argue the same ethos surrounded the process that culminated in Shout!, a double-disc affair with a reinvigorated Gov’t Mule. After a yearlong hiatus in 2011 and less touring last year—as Haynes was gigging with his own Warren Haynes Band in support of Man In Motion—the band used that time to write new material.

“We were able to gain some perspective based on having time off and looking backward at what we had done,” Haynes says. “We wanted to move forward but in a way that sounded like us but not anything like [what] we had done in the past. We were able to connect the dots a little bit better having that perspective.”

The 11 songs—three recorded at bassist Jorgen Carlsson’s Los Angeles studio and eight cuts at Carriage House Studios in Stamford, Conn.—are as strong as anything that the band has recorded.

“As diverse as this record is, nothing seems out of place,” says Haynes. “That took a lot of us musically putting our own stamp on the songs because the songs themselves are extremely different from each other. It was the way we played together that glued them together.”

It’s all a matter of perspective. No one familiar with Gov’t Mule’s music will think Shout! sounds like it came out of left field—Haynes’ spry but heavy guitar licks are there, Matt Abts’ no-frills punchy drumming still rides atop Carlsson’s deep grooves and Danny Louis’ keys still create subtle but substantial depth.

However, for those with a more intimate knowledge of Gov’t Mule’s musical canon, Shout! does offer something fresh. Of particular note is Haynes’ voice, which is in as fine a form and is likely the result of the musician’s commitment to leading a healthier lifestyle.

“I play differently when I don’t have to think about singing,” admits Haynes in comparing his two most recent studio projects. “And I sing differently when I don’t have to think about playing guitar. With Man In Motion, the fact that there were two keyboard players playing constantly and I didn’t have to play a lot of rhythm guitar freed me up to sing more like a soul singer. If I’m the only guitar player and do that, it becomes a little much, sometimes. These are subtle differences in approach. They’re challenges that I welcome but that I’m faced with.”

Shout!’s languid “Captured” sounds almost like a The Dark Side of the Moon B-side with mercurial, reverb-dusted guitar and key lines. Elsewhere, the segmented “Whisper in Your Soul” ebbs and flows like a classic Traffic tune with its shifting rhythms, while “Scared To Live” flirts with reggae. (The band released a dub version of their 2006 album, High & Mighty, which they called Mighty High.) “Stoop So Low,” meanwhile, written by Haynes and Louis, was inspired by the 40th anniversary of Sly & The Family Stone’s Fresh.

Lyrically, Haynes says, “a lot of subject matters that I was writing about could start to blur together. It was important to me to force myself into other areas even if they seemed lighthearted—even typical in some ways. It was an opportunity to start expressing myself lyrically from a direction that I felt was fresh territory to me.”

While not immediately obvious, a key example of the new lyrical territory is “Forsaken Savior,” which was inspired by the Arab Spring of 2011 and the forced resignation of Egyptian president Hosni Mubarak. “It started me thinking of a political figure, pop culture icon or superstar that made a few of the wrong decisions,” he says.

What’s fascinating about Shout! is how it allows the listener to evaluate Gov’t Mule’s music with its double-disc setup: Disc one features Haynes singing all 11 songs in his rough-hewn Southern soul style, while disc two features the exact same sequence of songs with guest vocalists replacing Haynes.

Hearing Jim James (“Captured”), Grace Potter (“Whisper in Your Soul”) and Ben Harper (“World Boss”) recast these songs in their own signature voices with Mule as the backing band give them an entirely different existence.

As the band was cutting “Scared To Live,” they came to refer to a particular part of the song as the “Toots section,” as they thought it sounded like something Toots Hibbert and The Maytals would do. Serendipitously, Hibbert’s people had contacted Haynes a short while earlier about possibly appearing on the reggae legend’s next album and it got him thinking about adding guest vocals.

“When I recorded ‘Funny Little Tragedy,’ I knew it was more like The Clash or The Attractions than anything Gov’t Mule had ever done and more than I’d ever done,” Haynes says of how the idea of the second record fully came into being. “I’d been hanging out with Elvis Costello recently and decided to email him about what kind of microphone I should sing through because I’d never done that kind of vocal before.” (The song vamps like a classic Costello tune in the vein of a harder-edged “Watching The Detectives.”)

Costello wrote him a long email back and said, essentially, to use a cheap microphone like a Shure SM58 to get the trashy garage sound that he wanted. The interaction got the band thinking about how cool it would be to have Costello sing a verse of the song but they didn’t immediately pursue it.

Finally, while “Stoop So Low” undoubtedly had a Sly-vibe, on playback, Haynes also heard Dr. John’s influence. As luck would have it, they were scheduled to tour with him three weeks later. Wouldn’t it be cool to get him on the record, too? What if all three said yes? And if they did say yes, why limit them to a cameo? Why not have them cut the full song?

Later, during the Love For Levon benefit concert last fall, Haynes thought that Jim James was a perfect fit for “Captured.” Shortly after writing “Forsaken Savior,” Haynes began thinking about the material like “Long Black Veil” that he’d heard Dave Matthews and Emmylou Harris perform together. (“Forsaken Savior” could fit neatly within Matthews’ emotionally tortured oeuvre.)

It became an odyssey of finding the right people for the right songs. The result is that, while the instrumental portions of both records are similar save for a few slight adjustments to the arrangements, the vocals create two distinct collections of songs.

Another project where Haynes has recently pushed himself is the Jerry Garcia Symphonic Celebration, which, as the name suggests, pairs the music of the famed musician with orchestras. The Garcia Estate contacted Haynes to see if he’d be interested in helping spearhead the project.

“It was a huge honor for me to be thought of that way and I love those songs,” he enthuses. “I was allowed to be the person who would pick the material and pick the arrangers. I spent a lot of time narrowing down songs, mostly to come up with songs that I felt like would marry themselves properly to a symphony and more important, that the symphony would elevate to another place.”

During an eight-show tour this summer, the celebration visited iconic rock venues ranging from Red Rocks Amphitheatre and the Greek Theatre to classically based facilities such as Tanglewood and Davies Symphony Hall. Haynes also recruited Steven Bernstein, Sean O’Loughlin and Chris Walden to help with some of the arrangements. The shows were warmly received.

“It could have easily been ones of those things you have nightmares about,” he says of a slight slip-up on the opening night in Raleigh, N.C. In Philadelphia, there were monitor issues that necessitated them being entirely shut off at one point. “The string section didn’t know where they were and there was a moment where I was listening and going, ‘Uh, that’s not correct,’ and it corrected itself fairly quickly. But again, it was that moment of panic with a symphony where it could have completely gone off the deep end.”

Though stressful, it’s these new musical adventures that Haynes strives to be a part of. And while they’re vastly different than what he does with Gov’t Mule, something he says in reference to the band’s, early days resonates with how he continues to carry himself as an artist.

“One thing I have tried to explain to people, which is hard to put into words, is that I don’t think we ever had the intention of carrying that exact mission throughout the next two decades,” he says of the group’s early and loose improvisational efforts. “Even if [Allen] Woody had stayed alive, our mission statement would have constantly changed. We would have felt like, ‘OK, we’ve done that. Let’s do something different.’ That’s where I am now.”