Rock musicians talk about second albums being like painful births, but rarely is it said of album number six. If you’ve survived that long, you’ve hit your stride: you know precisely how many slices of ham and shades of M&Ms you want on your rider, exactly how you like your drum kit tuned, and the ins, outs and whereabouts of your sound. Which, since you’ve lasted this long, is now as familiar and ingrained in your psyche as brushing your teeth. Album Number Six is your Purple Rain, your Aladdin Sane, your Highway To Hell. Band members may have come and gone, but when it comes to número seis, the rest just comes easy. Doesn’t it?

For Josh Homme, formidable leader of Queens of the Stone Age, however, his album six has been his toughest yet. In fact, Like Clockwork, almost didn’t happen at all. “I wish there was a different story to tell about how the record started, I really do,” he says, pacing backstage before the band is due to perform on Later… With Jools Holland. “When you’re making your first and second record, you’re just chasing inspiration and trying to keep up with it. But when you’re on your sixth, you go through some crazy ups and downs. Music is my religion and I’m trying to figure out who the fuck I am and how this all works. So this record was born of feeling lost. I was just lost, man.”

In the years between Like Clockwork and 2007’s Era Vulgaris, it looked as if Homme had just been busy. He produced Arctic Monkeys’ third record, Humbug, joined his mates’ bands, Them Crooked Vultures and Eagles of Death Metal, and had a second child with his wife, Brody Dalle. In 2011, Queens of the Stone Age regrouped to play Glastonbury and all was hunkybloodydory.

Or so it seemed. Later that year, things took a turn for the worse. Homme underwent complicated knee surgery and was bedridden for months afterwards, battling sickness and depression. The singer and guitarist later told journalists that his heart had actually stopped and, even though he was revived, how he felt like part of him had been left behind on the operating table. As one of the world’s steeliest (not to mention tallest) rock gods, who has always seemed as slick as his strawberry-blonde quiff, that kind of talk is somewhat unsettling. No wonder a new album was also the last thing on his mind.

Luckily, if anyone can find you in a storm, it’s your friends. Josh’s bandmates, Troy Van Leeuwen (guitar), Dean Fertita (also guitar), Michael Shuman (bass) and Joey Castillo (drums), managed to persuade him to start a new record at his Pink Duck studios in California. He also called up his mate Trent Reznor from Nine Inch Nails and asked him to produce it. In the end, Trent’s own musical commitments won out and he only appears on the weird and woozy ‘Kalopsia’, but it was enough to grease Homme's wheels. “Work has always saved me. It’s fucked me up, too, but it’s always pulls me out of trouble,” he says, about to launch into one of his articulate metaphors. “You’re pushing this boulder uphill and finally the thing rolls downhill and clears out a big pathway for you, so you finally know where to go. I think you spend a lot of time pushing that boulder uphill and when it finally goes over the cliff, you can see where your hard work is headed.” And hope to God that it doesn’t squish you? “Exactly. That’s why pushing it is important. Because if you fuck it up, you’re destroyed.”

But, as the album title mocks, everything kept on fucking up “like clockwork”. While Homme started to push, another band member began to pull. In the midst of recording, he ended up having to fire the band’s drummer of ten years, Castillo. Homme won’t say much about his departure, though Castillo has suggested in interviews that punishing tour schedules with both Queens of Eagles of Death Metal eventually took their toll.

Homme, meanwhile, hints that differences, musical or otherwise, forced them apart. “Friends are people who have parallel interests,” he says matter-of-factly, “and I gave up being upset when someone’s life takes a different direction long ago. It’s not a reflection of what I’m doing or what they’re doing, it’s just the way it is.” While other bandmates would smash up their instruments and vow never to speak again, Homme looks at it a little more philosophically: “If you’re friends with somebody and you don’t wanna make music with them anymore because of the different paths you have to take, you should be able to still be friends.”

Friendship, more than anything, is Like Clockwork’s nuts and bolts and Homme ensured his album was stuffed with more of them than ever. A dream dinner party line-up, he rounded up Jake Shears from the Scissor Sisters, with whom he kick backs and watch Games of Thrones, Alex Turner from Arctic Monkeys, who he takes motor biking, and his long-time collaborator Mark Lanegan into his studio to appear on the record. The band even invited British illustrator Boneface, who created Like Clockwork’s creeptacular visuals, down to Pink Duck to hang. If their eventual performance on Later… is anything to go by, where he sat motionless in a bloodied motorcycle helmet, Boneface looks to have become an eccentric extension of the band, the latest in a roll call of bit players in Queens of the Stone Age’s movie epic. Finally, one of Homme’s most famous greatest friends, Dave Grohl, who had previously played on 2002's Songs For The Deaf, dropped by to fill in on drums. He smashed through the album’s remaining songs, except on the title track, where duties fell to new touring drummer Jon Theodore.

During a particularly miserable time, these guest appearances were welcome interruptions. “It was nice to have visitors, so we didn’t have to pay attention to how not well it was going,” laughs Troy. “In one week, Joey and us parted ways, two days later Dave Grohl played with us, and two days after that, Elton John was in the studio.”

Elton is the first most unusual appearance on Like Clockwork. Queens have always been known for their guest stars, but this one was starrier than most. Not one eyebrow went unraised when the album’s promo material landed in music journalism’s collective inbox. But, as is typical in Josh Homme’s world, the collaboration came about quite simply. His old roommate happened to be Elton John’s driver, and played him some Queens of the Stone Age, which John liked so much he just had to get in touch. “I got a phone call at my house on a Sunday out of the blue,” says Homme, “and at the other end the line someone said [puts on a plummy English accent], ‘Josh, this is Elton’. And I said: ‘Yeah, yeah, I know’. Then I got a text from my old roommate that said: ‘Elton John’s gonna call you in five minutes’. I was like, Jesus, where were you ten minutes ago? Then Elton said: ‘The only thing missing from our band was an actual queen. And I told him [goes camp]: ‘Honey, you have no idea’.” He’s told this story a hundred times already, but it still makes him smile. “The first thing we did was make each other laugh, so it eased the pressure cooker of excitement. Because sometimes excitement can be stressful, you know?”

Josh needn’t have worried, though: Elton wanted to get his piano parts right just as badly. “He got pissed at one point because he didn’t think he was learning the song fast enough,” says Troy, of how they were tracking the song live, “but we were like, ‘Dude, you’re really good!’. “In the end, it went so well that it gave us hope. That was all we needed to keep us going.” Elton left the studio halfway through to back to his regular job – recording with Engelbert Humperdinck – but returned to sing on the rest of the Queens track, called ‘Fairweather Friends’. “It blew my mind,” says Homme. “[In the end], I think that we did something exciting for both of us. It was like sitting in a catapult together and going ‘cut the rope!’”

That’s not Like Clockwork’s only unusual twist, however. Besides the album’s new sound, which twists their signature sun-baked stoner riffs and dense triple-pronged guitars up with dusty R&B, metallic funk and the sounds of 60s-era Cali-for-nigh-aay, another unprecedented appearance comes Nick Oliveri. The former QOTSA and Kyuss member pops up on 'If I Had A Tail' with Turner and Lanegan. To the best of our knowledge, Homme and Oliveri weren’t chums and hadn’t been for ages, ever since Homme booted him out of the band, allegedly for beating up his then-girlfriend. In fact, they had the music press absolutely fooled. “I’m still friends with Nick, I’ve been friends with him since I was 11,” says Josh, amused at the idea that their decade-long feud has been completely fabricated. “But, because he and I have been friends since three months after we parted ways musically, I forgot to give a shit to tell everybody. It feels like nobody’s business.” He pauses. “The truth is that I fired my best friend. I drove to his house and looked him in the face and I told him the truth.” In the same way, one imagines, that Homme told Joey Castillo.

With all of the turmoil, not to mention the album’s accompanying gory visuals and that Homme wanted industrial warlord Reznor to produce it, you’d be forgiven for thinking that Like Clockwork was going to be as bleak as the Elephant & Castle shopping centre. However, says Troy, its inky-black undertones are open to interpretation. “We went to the Louvre the other day and none of us had ever seen the Mona Lisa,” he begins. “There was a huge crowd around it and the tour guide was saying that the sort of smile she has depends on your mood: if you’re in a good mood, you see her mouth curling up, but if you’re in a bad mood, it turns down. That’s the way we see our record: some people think it’s dark and others think it isn’t. I welcome that; that’s what art is about. But to us, [the album is] a reflection of trying to say something that’s really difficult, and turning and facing it and going: ‘OK, I’m just going to barf this out’.”

In many ways, after all of the ups and downs, and all the hirings and firings, Like Clockwork couldn’t help but be Queens of the Stone Age’s most personal and soulful album yet. “The undercurrent of the record is just be honest, and if something is scary, walk toward it, not away from it,” Josh confirms. “There’s no other way I could have said any of what it says. I just want it to feel real. I think: if I do this from a real spot then [we] could be someone’s favourite band in the whole world. And, ideally these records, if you do ’em right, make you a little better as a person. Especially for me. I don’t work at a fucking bank, so I’m gonna bleed for this shit until all the blood’s gone.”

Making an album may be an expensive and bizarre form of therapy, but Queens of the Stone Age’s Album Number Six has certainly paid off.

Like Clockwork is out on Monday 3rd June.