It seems that a lot more people have developed deep feelings towards the newly 60-year-old Australian songwriter (whose recent prompts several congratulatory yells from the crowd tonight) and his six-strong troupe of compatriots lately. 30-odd years on from their debut album, Nick Cave & The Bad Seeds are touring arena-sized venues for the first time. What makes this remarkable is that the album at the core of tonight's epic, two hours plus set, last year's haunted and haunting Skeleton Tree, is by some distance their most experimental. Driven by a steadfast determination to confound expectations and routine in both songwriting or musical presentation, it's the kind of a brave, challenging yet immensely rewarding undertaking that's usually doomed to weed out fairweather fans. In the case of the Bad Seeds, it's deservedly cemented the band's gradual rise from a perpetually black-clad cult act balancing precariously on the brink of chaos to something approaching a mainstream concern, albeit one that won't opt for easy answers in their search for greener commercial pastures.

For all its immense strengths (and we could well be looking at the most impressive album yet from an act that has never managed to make a bad record), Skeleton Tree's fractured, churning soundscapes and perpetual sense of staring unblinkingly at a grief-filled void (the album was recorded after – though, interestingly, written before - the tragic accident that led to the death of Cave's teenage son, Arthur) seem more suited for quiet contemplation than huge venues that are more accustomed to hosting fist-pumping arena rock and pyrotechnics-bingeing pop acts.

Any fears about the new material struggling to connect in these vast surroundings are squashed as soon as Cave gets up from the chair he's perched on for the, er, skeletal opener "Anthrocene". Cave stalks the stage like a caged beast looking for a carelessly sealed exit whilst the Bad Seeds pump up the disjointed, stuttering percussive clatter of "Jesus Alone" until this haunting ode to senseless loss becomes foreboding enough to act as a warning siren for an impending apocalypse.

It's a stunning performance but the band are still only warming up. From 1985, a positively fiery "Tupelo" rages and howls like the storm of biblical proportions the song's describing. The ominous, borderline deranged stomp of the title track of The Bad Seeds' 1984 debut From Her to Eternity is delivered with a white-knuckled fury that most acts would save for the encore. It seems that dismantling the Bad Seeds house style for Skeleton Tree has reinvigorated an operation that was in great shape to begin with: Nick Cave & The Bad Seeds used to be a great live act. Tonight, they are phenomenal.

But tonight's set is not just about unleashing the full force of The Bad Seeds. Preceded by Cave's brief speech about the privilege of being able to perform at the reopened scene of the May 22nd terrorist attack, "Into My Arms" accrues additional gravitas and poignancy; the nearest thing to a standard in the Bad Seeds catalogue, Cave sings the 20-year old song like it was only written yesterday. The more contemplative cuts off of Skeleton Tree also shine in live setting. Slow and stately to the point of virtually standing still, the mournful chords and unfathomable sadness of "Girl in Amber" are nothing short of majestic in their desolate beauty. For all its varied and ample strengths, Nick Cave & The Bad Seeds' music has never been this moving. Tonight, an ability to chart and channel the deepest depths of sorrow is effortlessly added to the band's emotional palette.

"Don't touch me", Cave whispers at the end of "Girl In Amber" but that admonishment certainly doesn't apply to tonight's audience. ''Look at me now!'', Cave barks repeatedly as "Jubilee Street" careers into yet another pummelling crescendo. It's impossible not to. Cave has always been a spectacular performer but he's working overtime tonight to bridge the arena's vast distances. Lunging himself relentlessly at the front rows and turning the barriers in front of the stage into an impromptu catwalk in order to better rain disturbing visions at the faces of the gathered faithful, Cave engages hecklers in conversations, accepts a tissue proffered by a fan with a gracious "that's very considerate of you", and even finds time to deliver a mid-song cease-and-desist order to a fan who keeps heckling stuff about his socks. "The Weeping Song" finds Cave venture deep into the audience to orchestrate the song's handclaps from the backrest of a row of seats, surrounded by fans who can't quite believe what they are witnessing.

In lesser hands, such tireless showmanship could risk seeming more than a bit over the top, but Cave - the most naturally strutting rock cockerel this side of Iggy Pop - instantly has the crowd on his side: when he calls for people to get closer to the stage, the entire sold-out standing section instantly responds affirmatively as one. By the end of the evening, Cave takes off his sock and tosses it to the fan he earlier told off for obsessing over his footwear: clearly, here's a performer who's willing to give his all, up to and including his clothes.

Stood impassively behind their wildly rampaging frontman (you feel sorry for the overworked technician whose job is to scoop up the various bits of kit that Cave tosses aside when the spirit compels him to move), the Bad Seeds' scope - the split-second switch from a slinky graveyard funk groove to a few bars of tooth-melting cacophony during "Red Right Hand" is a particularly potent display of the band's masterful grasp of dynamics and near-telepathic interplay - and ability to apply their tools sparingly for maximum impact remain second to none. Instead of his trademark violin solos, generously bearded Warren Ellis spends the majority of the set strumming his violin like a tiny four-stringed guitar or holding it in the air in theatrical angles that suggest we're observing an overdue sacrifice to a vengeful god in order to unleash growls of feedback. When the mournful spot of soloing finally arrives, it elevates the wounded hope of "Distant Sky" to almost unbearable levels of poignancy.

Cave has spoken of not wanting these live shows centred on the grief-stricken Skeleton Tree to be a downer. By the time Cave invites a few dozen fans - including a boy in a Bad Seed shirt who can't be much older than 10 but knows all the X-rated lyrics by heart - on stage to shimmy to "Stagger Lee" such fears are wiped out as comprehensively as the devil who meets his grisly fate in the new verse Cave's added to this brilliantly overblown reimagining of the traditional American murder ballad. The roots of the Skeleton Tree tour may be in an unimaginably painful tragedy, but Cave & co. have managed to turn this premise into a jubilant, awe-inspiringly powerful celebration of the restorative potential of music.