Nineteen years after the Boys Next Door fell into the bar room sprawl of urban Caulfield, Melbourne, Mick Harvey still has problems getting his head around his enigmatic popularity. An unfamous man at heart, Harvey treasures his private universe, finds it just strange that anybody should wish to hop on board the Nick Cave and the Bad Seeds train to nowhere, to the emotional shredland where primitive passion slashes razor sharp with the heart's deepest desires and fears.

Yet, as backdoor man as he might wish to be, fame is trailing Harvey, sniffing at his well-worn boot heels. Knocking at his front door. Two recent Cave biographies lay a significant slice of Cave's cult demi-god status at Harvey's feet.

To his utter surprise, the last Bad Seeds "side project", Murder Ballads, has already sold a staggering 600,000 copies worldwide, virtually doubling the sales of their previous masterpiece Let Love In, his beautifully executed Serge Gainsbourg tribute Intoxicated Man gathered a clutch of sweaty reviews and more than a few friends, and now his name shares slick billing with Cave and fellow Bad Seed Blixa Bargeld on the soundtrack to the new John Hillcoat film To Have And To Hold.

That, ostensibly, is the reason we're here. The last time Cave, Bargeld and Harvey soundtracked together was Hillcoat's bleak, brutal, politic, polemic Ghosts... of the Civil Dead. By contrast Hillcoat, a former director of rock videos - believe it or not, spins a different take on his ghosts in To Have And To Hold, a tough, disturbing, brooding, almost malevolent, creeper of a psychological thriller that spins obsession, lust, envy, fear, guilt and - eventually - blunt unequivocal madness into a draining scrape of the psyche.

Shot with dazzling impact and vast ambience in the remote Sepik River region of Papua New Guinea, To Have And To Hold incants the dynamics of Apocalypse Now in its dark passage. Insanity, extremes - love and hate waltz together so sweetly, and passion drenched and wrenched... of course, St Nick and co had to soundtrack it.

Harvey chuckles, "Yeah, I guess so. It's very harrowing, quite dramatic and a little bit overblown, but deliberately so. Part of John's idea was to make a film that was like a '40s or '50s melodrama so it has those melodramatic aspects. We could even over-indulge and not worry about crossing the line into melodrama with the music as well on this occasion because it was actually what he's aiming for."

As fascinating as the dynamics of the film's core though are those of putting the core Bad Seeds trio in a studio on a different tangent to normal.

Soundtracks are a totally different musical sheet to the group score. As Harvey says inevitably the visuals often dictate what composers can get away with musically, that and the sense, the psychology and characterisation raining from the screening. "You just follow your nose, really," he says, before unravelling a rare glimpse of how these three similar - but also radically different - men define their turf within the creative process.

These are men of strength and pride: toothy, craggy, strange, shadowy men. The best of the Bad Seeds comes from the fine balance between their ying and yang, the possibility that it all could explode at any second, and the unique invention that comes at the point of unity.

"In the case of Ghosts they actually asked Nick and Blixa to do the soundtrack," Harvey says. "Nick was obviously meant to supply the more melodic element and Blixa to work on making music out of the machine noises and so forth, and they were meant to kind of overlap somewhere, where the noises and music all became one..

"Nick and Blixa basically turned round and said that's all very well but neither of us can play any instruments really so we'd better get Mick to it. So working on all those different source sounds which Blixa was still doing a lot of in this film as well and musical elements like that and making loops and things, everybody kind of crosses over in the end.

"Nick kind of wrote a couple of the main melodic themes this time then Blixa and I more or less did the other one. Then the way they got arranged was kind of everybody together so it's hard to draw the line really. Sometimes themes overlapped and became entwined with one another, In the end it becomes this vast thing when you're all writing and arranging together.

"The soundtrack are a very different part of the art form. It must relate to what must have been theatre music in the past or even writing music for ballet or opera, what that would have been like in the past. You're writing music to the choreography of editing or even quite specifically to the choreography of movements and action that's going on up there. It relates to many traditional kinds of forms."

It's Harvey the composer talking. This is his turf. Something he will point out in not so blunt a fashion a few minutes later. But it's also something Bargeld and Cave understand. And it's why this partnership works.

Hillcoat wanted a "big lush 50s style score". Harvey chuckles at some private irony. "in the old school style, more along the lines of Bernard Herrmann would do. Apart from the main romantic theme, I can't imagine Bernard ever getting that mushy but the other elements aren't that far away from a Herrmannesque sort of score."

Yet it is indelibly stamped with Cave, Bargeld, Harvey. It's something to do with the tension and the seeping emotion, the unspoken romance and the ever-present faint whiff of violence. Of not quite right.

And asking and expecting such a score from them isn't so odd. The root of Bad Seeds quietnesses, their moody tenures, the strangled balladry and rich almost Wagneresque, perhaps Goethe, poetry and Gothic bravura of those lonely pastures where Cave's voice plays havoc with the Seeds sparse music float, delve deeper than the confines of rock - no matter how extreme the extremes - into the spectrum of classics, the music hall and orchestration.

The Bad Seeds with strings is mood personified. Harvey agrees noting that dramatic orchestration and certain classical composers fall well within the trio's shared "field of interests".

Ultimately, though, it is Harvey who finds most fulfilment in such situations.

"I like working on films a lot, actually," he says. "I'm not a songwriter. I always work on the music and the musical arrangement. It's what I always do. I think it's a bit different for Nick, and possibly for Bliss, because they're both lyric writers and singers, primarily songwriters.

"Nick was really interested in the whole thing up to a certain point and once it was kind of recorded and he'd done his bit, he didn't really know what to do any more.

"He sort of lost interest in it because (there's a wry chuckle) he'd done his job. He couldn't go out and sing the vocal on it then. It was sort of over for him and he just went home early actually and left me to kind of mix and do all those sort of things. Which is completely fair enough too.

"So for him it's good, for me it's very fulfilling. Nick really likes it compositionally but I don't think it could be as fulfilling for him as the songs he writes. For me it's as good as anything else I do - and just as important."

To the Mick Harvey interview - Part 2: Nick Cave and the Bad Seeds... the new album revealed