We came for a knockout of a CD release party, and we got something far more important: a reassuring nod and — blink and you missed it, for this was ostensibly a "no frills" Mule show like any other proof that after four years of reinvention, the idea of Gov't Mule undergoing a real rebirth is no bullshit.

Gov't Mule is no longer a collaborative it's a band again. The comfort zone and the joy that that realization brought was slow to dawn on attendees during this well-sold Monday night at Roseland: a three and a half hour, somewhat frustrating, patience-testing, guest-less show that devoted the entire first set to brand new material and cut the second set short due to curfew.

But it was there. And it is something great to behold.

First amen: The new tunes kick ass

For once, a band has made good on its promise and done exactly what it said it was going to do: the brand new songs on Deja Voodoo sound like old and new Mule, and perhaps more importantly, sound like the most natural progression possible from the Deep End discs: the old school Mule grounds them, but they tackle almost the full range of Mule styles and instead of being tunes that have to merely accommodate keyboards and a bassist who isn't Allen Woody, they are songs that are as much Danny Louis and Andy Hess as they are Warren Haynes and Matt Abts.

Deja Voodoo is a deeply involved disc, the Mule's darkest and most intense yet, and the type that, annoying and rock crit chic as it is to say, is best imbibed and subsequently grasped with repeat listens. Some songs are definitely better than others, but all came to life in one way or another during the first set at Roseland, and applause to the Mule for chewing its own second set time to give these nuggets the workouts they deserve.

You have your straight up Mule gassers — the opening "Bad Man Walking," "Perfect Shelter," and "Mr. Man," for example — destined for the go-to, dependable ripper slots in the setlist (i.e. the same punchup effect that opening with a "Bad Little Doggie" or hammering it in during a mid-set lull provides), played straight, hard-nosed and rarely, if ever, messed with. Then you have your centerpieces, which depending on the band's mood (and Warren's lead) explode into cacophonous, psychedelic hailstorms or moody, brooding rockers: the Floydish/King Crimosnesque "Silent Scream" (an audience slayer among many at the Roseland show); the prickly diatribe "About to Rage," the gritty, spaced-out blues "Slackjaw Jezebel," and the broken morality tale "New World Blues."

Then there are the songs that push this thing over the proverbial line, and scintillating, frisson-filled live renderings only confirmed their destinies as Mule staples. "Lola Leave Your Light On" is Bad Ass — the no frills cock rock tune that scratches the Zeppelin itch and gives Warren the chance for some curled-lip raunch, both on vocals and guitar. "My Separate Reality" simply floors, a marriage of Haynes' finest, slow-to-boil-over drear (think "No Need to Suffer," "World of Difference," that sort of stuff) and the more introspective, dour-as-all-hell devastators ("Tastes Like Wine") he delivers best during solo acoustic outings. Mighty and undeniably well-done stuff, all of it.

Second amen: The Mule is four now, not two plus two

Danny and, especially, Andy no longer feel like guest musicians to the audience, and the Mule didn't need a banner change (the background stage banner in the first set, which was the contorted griffin-like creature that graces the front of Deja Voodoo, changed to the classic, red-and-black mosaic-like Mule banner for set two) to prove it. Louis is comfortable such that he has no problem adding fills, colors and runs to Mule tunes in places where they weren’t before, and no problem stepping up to challenge Warren in the solo improv arena in places where, in past years and Mule adventures, he played things straight and safe. "Blind Man in the Dark," which closed the second set, is quickly becoming his tune (the amorphously expanded solo section, which first jelled during Karl Denson's brief stint as a featured guest in spring 2003, has coagulated into a dynamite Hammond B3 playground), and he's also a force to be reckoned with on traditionally Haynes-dominated tunes like "Thorazine Shuffle." He still reaches sometimes for a peak that, by way of a sloppy exploration, won't be there and needs to find a better way (instead of just sort of collapsing out of it) to bail out of a failed experiment, but it's clear he's a weapon now, not just an addition, and the band knows it.

It's Hess who's had the time of it, and his presence still lacks in some areas, but just to hear that cocksure rumble that kicks off "Thorazine" again and knowing he'll be able to hold it down and won't have to rely on Abts so much is refreshing. Hess is coming, if not here yet — he's getting the gist of when to jazz-dance beneath the lead players and when he really needs to throw the anchor and just groove. Abts, still the scene's most criminally underrated drummer, feels it too — he doesn't have to lean so much to the bass now that it's not shifting players every other song, and while it will be a while before he molds a solid performance rapport with Hess into an E.S.P. one, the dynamics are jelling: Abts knows he can rely on Hess if he wants to get a little fancy, same as he's willing to follow Hess's lead if the bassist sparks an idea of his own. Matt Abts the Hammer remains this band's rock.

Third amen: Warren Haynes is starting to relax again, both as a player and a bandleader

It's not as if Warren never had those "out" moments of truly mind-altering guitar work during the Deep End tours, or didn't have fun (and provide it for the audience) welcoming every great musician in his Rolodex to share his stage in the past three years, but Mule fans who remember what Haynes was like in his wild, unrestrained all-meat days (think early 90s ABB and beginning Mule), or are at least familiar with recordings from those formative years can tell that the Warren of recent years been erring on the side of tethered more often than not.

It's not that he's tired at all (or maybe he is), nor does it have anything to do with the Allmans (where he remains the raw meat stalwart to Derek Trucks' stringier, more experimental fare) or the Dead (he's right for this band and he isn't, but that's a discussion for another time) — we're talking Warren Haynes, lead singer and lead guitarist of Gov't Mule.

Mostly, it has been one discernible habit in particular: the tendency to become "Captain Warren," and worry more (understandably so, given the rotating cast) about the band and holding it together in a jam than getting into his own zen sphere and cutting loose with the same balls-out gravitas we all love him for. You hear many musicians that have played with Haynes (Panic's Dave Schools for example, in the Deepest End interviews) talk about how he likes to "cut throats" and "let the floor drop out" and fun-to-say stuff like that, but during the Deep End period, it's clear that those moments happened somewhat less during the band's rebuilding period — they were replaced by more collaborative, guests-are-doing-something-totally-awesome-in-the-moment stuff, but where's Warren just stepping to the front and pillaging an audience?

To an unpracticed ear for his hellhounded, exploratory soloing, this reticence was probably unnoticeable, but Warrenheads know that he uses relied-on licks (as most marquee guitarists do) quite often, and when he's out of ideas in a solo, his go-to vault for improv resources leaves his playing naked and rather repetitive. This happened far less than another habitual occurrence, however: even when he was getting on a marvelous creative tangent (often) in his soloing, he seemed often too nervous about what the rest of the band was doing to follow it, closing off solos just three or four bars too early, as if he wasn't willing to really stretch out and fire into orbit for fear the rest of whomever was on stage with him that night wouldn't know how to catch him.

But not recently, and certainly not tonight. Haynes was a ballast, a machine gun and a machete at Roseland, exciting eyes and knowing ears watching him build those old school, gutting solos to their exploding climaxes and shivering peaks, hoping he holds off before noise damage ensues but at the same time begging him to just pour the whole damn can of gasoline on the fire. He teed off during the second set with hands and words during "Thorazine," "Blind Man" and a marvelous run-through of Al Green's "I'm A Ram," while offering jazz-cadenced, more reserved, but no less core-cutting contortions on the tunes that required them, such the textured jam that bled from "Larger Than Life" into "Birth of the Mule." The only real weak spot was the set-opening "Soulshine," which is always wonderful to hear, but perhaps more than any other Mule tune suffers considerably when its soul-lifting improvisational section is truncated and perfunctory, as it was tonight.

The show's encore was a sizeable treat all in itself, from a band that prides itself on providing them. A few tuning strokes from Warren and, as the first of two songs began, in crept a vaguely familiar, gorgeously pastoral progression that first sounded like "Into the Mystic," but quickly became a majestic rendering of "Ballerina," a rawer Van Morrison chestnut several years older than "Mystic," found on the immortal Astral Weeks (1968). In Haynes' ongoing quest to tackle the Morrison catalog (and this Van fanatic is holding out in giddy earnest for the day he attempts "Cyprus Avenue," "Astral Weeks" or, preferably with horns, "Caravan"), "Ballerina" is a curious, mature and rewarding choice: slightly obscure (although it was still embarrassing how many Roseland attendees didn't seem to know it), and epitomizing the rawer, more unrefined antecedent to Van's beloved "Caledonia soul" that got further and further away from the gritty R&B of Them with each successive album in the early 1970s.

As if to clear the air after all that headiness and ethereal beauty, Mule busted into its terse arrangement of Robert Johnson's "32-20 Blues," which over the years has become one of the band's most reliable vehicles: a necessary injection of ballsy blues whether the set needs it or not, and an unchecked, elastically-jammed showcase for Haynes and whomever he's chosen as a foil. This is one of Mule's more reliable "guest tunes," especially for sitting-in guitarists (all-time versions include the Live With a Little Help from Our Friends slugfest with Derek Trucks and Chuck Leavell, The Deepest End with Sonny Landreth, Will Lee and Karl Denson, and, most recently, the Telluride Nawlins'-soaked scorcher, guest starring the Bonerama front line). Here, Haynes threw the improv baton at Louis, who answered with punch, and then yanked it back, peeling off sheets of Les Paul gristle, his fingers racing up and down the fretboard, wringing slide licks out of the thing as if he were with his bare hands extracting sap from a maple tree. With that crazy, lemon-faced "Warren" look that means he's going to take it up a notch, Haynes tacked on a false ending to his solo, and then began to play call and response – with himself.

Tickling the high register and answering those pixie tones with syrupy moans on the low, it was an inspired bit of wankery from a pre-legendary guitarist who rarely lets his solos get that wonderfully ridiculous anymore. That's not a dig: Haynes is more in control of his guitar than some folks are of their fingers, and rips the shit out of it with largely peerless expert abandon, but to see him giddily jerking off on himself, if for but a scant minute, was even more confirmation that the Mule can finally relax and play with some fuckin' balls again.

The Deep End albums and concerts as a whole are important historical documents for this band, and in the no less than 26 Mule shows I saw during those years, I take away memorable moments from each. This Roseland adventure was the first time in four years, however, that going to see and hear this band didn't feel like Haynes, Abts & Friends – it felt like the Mule. They're a band again: an intensely musical, creative force to be reckoned with, with the brightest of futures.

We're lucky to have em.