Nel 1999 Nick sposa la ex modella e attrice Susie Bick da cui avrà due gemelli: Arthur ed Earl.

Ogni disco di Nick Cave sembra avere sempre un significato ben preciso ed una direzione decisa, No More Shall We Part, del 2001, è il disco della "redenzione".

Tematiche inerenti alla fede ed alla religione si rincorrono lungo tutto l’arco del disco, dove Nick si rapporta, spesso con tono critico, ad un severo Dio non ben definito.

Musicalmente, Nick, è accusato di aver pubblicato un album forse un po’ troppo manieristico, ma il tono del disco resta molto coerente a se stesso: suoni molto dilatati, atmosfere malinconiche – come quelle del singolo As I Sat Sadly By Her Side – che, di tanto in tanto, sfociano in isteriche reazioni come nei finali di Oh My Lord o di 15 ft. Of Pure White Snow.

Nick Cave & The Bad Seeds

Nel 2003 è la volta di Nocturama, la cui caratteristica “principale” è che si tratta dell’ultimo disco che vedrà la presenza di Blixa Bargeld in seno ai Bad Seeds dopo venti anni di carriera.

Il chitarrista tedesco motiverà tale decisione adducendo al suo voler esplorare nuovi territori artistici e lascerà la band nel marzo dello stesso anno, senza rancori di nessun tipo verso nick e la band.

Nocturama è, verrebbe da dire "di conseguenza", un disco di transizione, registrato in pochi giorni, ha il merito di tornare a toccare la sfrontatezza dei primi lavori di Nick, ma – al tempo stesso – soffre per la mancanza d’originalità e di quel tormento d’animo che tanto avevano caratterizzato i suoi primi lavori.

Nonostante ciò, nel disco, alcuni brani risultano comunque di notevole spessore, come Rock Of Gibraltar o la lunghissima Babe, I’m on fire.
Dopo la dipartita di Blixa, la band si assesta anche con una sorta di “avanzamento di grado” del violinista Warren Ellis, le cui qualità ed il cui carisma sono spesso in risalto.

Nel 2004 è dato alle stampe il primo disco doppio della carriera di Cave, trattasi di Abattoir Blues & The Lyre OF Orpheus.

In questo disco è praticamente impossibile non notare l’introduzione di un coro gospel presente in maniera massiccia in entrambi i lavori.
Il primo è caratterizzato da atmosfere forti ed adrenaliniche, il secondo è contraddistinto da toni quieti e riflessivi.

Il doppio album è molto ben riuscito e vario, dall’ottimo pop di Breathless, alla cupa Hiding All Away passando alle struggenti ed illuminate Easy Money e Spell.

Dopo il calo di tensione di Nocturama Nick Cave torna a vette che gli competono, ritrovando l’ispirazione da lui tanto (de)cantata in There She Goes, My Beautiful World, il suo mondo è sicuramente diventato più bello, ma non per questo privo delle intuizioni che l’hanno reso uno degli artisti più stimati degli ultimi 20 anni.

Il 2005 è l’anno di una raccolta di tre dischi titolata B-Sides & Rarities che raccoglie tutto il materiale inedito composto dalla band in più di vent’anni di carriera.