El proyecto que más tarde evolucionaría hasta convertirse en Nick Cave and the Bad Seeds comenzó tras la disolución de The Birthday Party en agosto de 1983. Tanto Cave como Harvey fueron miembros de The Birthday Party, junto con el guitarrista Rowland S. Howard y el bajista Tracy Pew. Durante las sesiones de grabación de los EP programados de Birthday Party, Mutiny/The Bad Seed, surgieron disputas internas en la banda. La diferencia en el enfoque de Cave y Howard hacia la composición de canciones fue un factor importante, como Cave explicó en una entrevista con On The Street: "la razón principal por la que The Birthday Party se separó fue que el tipo de canciones que yo estaba escribiendo y el tipo de canciones que Rowland estaba escribiendo simplemente estaban totalmente en desacuerdo". Tras la marcha de Harvey, se disolvieron oficialmente. Cave también dijo que "probablemente habría durado más, pero Mick tiene la capacidad de juzgar las cosas con mucha más claridad que el resto de nosotros".
Una versión embrionaria de lo que más tarde se convertiría en Nick Cave and the Bad Seeds se formó en el entonces hogar de The Birthday Party en Londres en septiembre de 1983, con Cave, Harvey (actuando principalmente como baterista), el guitarrista de Einstürzende Neubauten, Bargeld, el bajista de Magazine, Barry Adamson, y Jim G. Thirlwell.

La banda se formó inicialmente como una banda de acompañamiento para el proyecto solista previsto de Cave, Man Or Myth?, que había sido aprobado por el sello discográfico Mute Records. Durante septiembre y octubre de 1983, grabaron material con el productor Flood, aunque las sesiones se interrumpieron debido a la gira de Cave con The Immaculate Consumptive, otro proyecto formado con Thirlwell, Lydia Lunch y Marc Almond. En diciembre de 1983, Cave regresó a Melbourne, Australia, donde formó una alineación temporal de su banda de acompañamiento, debido a la ausencia de Bargeld, que incluía a Pew y al guitarrista Hugo Race. La banda realizó su primer show en vivo en Seaview en St. Kilda el 31 de diciembre de 1983.
Después de una corta gira australiana, y durante un período en el que no tenían management, Cave y su banda regresaron a Londres. Cave, Harvey, Bargeld, Race y Adamson formaron la primera alineación consistente del proyecto, mientras que la antigua novia de Cave, Anita Lane, fue acreditada como letrista en el álbum debut de la banda. El grupo, que hasta ese momento no tenía nombre, adoptó el apodo de Nick Cave and the Cavemen, que utilizaron durante los primeros seis meses de su carrera. Sin embargo, más tarde fueron rebautizados como Nick Cave and the Bad Seeds en mayo de 1984, en referencia al EP final de The Birthday Party, The Bad Seed. Comenzaron las sesiones de grabación para su álbum debut en marzo de 1984 en los Trident Studios de Londres y estas sesiones, junto con las sesiones abandonadas de Man Or Myth? de septiembre-octubre de 1983 que se grabaron en los estudios The Garden, formaron el álbum From Her to Eternity, lanzado en Mute Records en 1984.

Tras la marcha de Race y Lane, los miembros restantes se trasladaron a Berlín Occidental, Alemania, en 1985 y lanzaron un segundo álbum, The Firstborn Is Dead. El álbum estuvo muy influenciado por el Americana gótico del sur de Estados Unidos y la música blues, ejemplificado en canciones como “Tupelo” y “Blind Lemon Jefferson”, que hacen referencia al nacimiento de Elvis Presley y Blind Lemon Jefferson respectivamente. Lanzado al año siguiente, el álbum de versiones Kicking Against the Pricks exploró tales influencias más directamente con interpretaciones de material de Johnny Cash, John Lee Hooker y Lead Belly. El álbum de 1986 también marcó la llegada del baterista suizo Thomas Wydler, miembro de Die Haut, y contó con apariciones invitadas de Race, Pew, y el guitarrista de Birthday Party, Howard, quien había estado brevemente de gira con The Bad Seeds como miembro sustituto en 1985. La muerte de Pew por un ataque epiléptico también ocurrió en 1986.
La banda obtuvo un mayor número de seguidores debido a un segundo lanzamiento de álbum en 1986, Your Funeral, My Trial, que coincidió con la marcha de Adamson. Tender Prey, el oscuro y melancólico siguiente álbum de 1988, vio la llegada del guitarrista estadounidense Kid Congo Powers —Harvey hizo la transición al bajo— y el tecladista alemán de corta trayectoria, Roland Wolf. El sencillo “The Mercy Seat” narraba la historia de un prisionero sin remordimientos en el corredor de la muerte y aumentó aún más la aclamación crítica y la atención comercial del grupo. La pista recibió más tarde el honor de ser versionada por Cash en su álbum de 2000, American III: Solitary Man. A pesar del creciente nivel de éxito, los problemas relacionados con las drogas de los miembros de la banda se volvieron problemáticos. El documental The Road to God Knows Where, dirigido por Uli M Schueppel, narra un período de cinco semanas de su gira por Estados Unidos en 1989.

Cave y sus compañeros de banda también persiguieron otras ambiciones creativas por esta época. En 1987, The Bad Seeds aparecieron en la película de Wim Wenders Wings of Desire, y Cave también fue incluido en la película de 1988 Ghosts... of the Civil Dead, que coescribió con Race. La primera novela de Cave, And the Ass Saw the Angel, se publicó en 1989.

Después de un período en Nueva York, Cave se trasladó a São Paulo, Brasil, poco después de la gira final de Tender Prey y, después de finalizar con éxito un programa de rehabilitación de drogas, comenzó a experimentar con baladas impulsadas por el piano. El resultado de este período posterior a la rehabilitación fue The Good Son de 1990. Con un tono melancólico y anhelante, el álbum fue bien recibido tanto por la crítica como comercialmente, y produjo los sencillos “The Weeping Song” (con voces de Bargeld) y “The Ship Song”.

Dos músicos australianos establecidos, Casey de The Triffids y el artista solista y tecladista Savage, reemplazaron a los salientes Powers y Wolf. La incorporación de Casey en el bajo permitió a Harvey volver a la guitarra. Su siguiente disco, Henry's Dream de 1992, marcó un cambio hacia un sonido de rock más duro. El productor David Briggs, conocido por su trabajo con Neil Young, fue contratado para el proceso de grabación. La gira del álbum está documentada en el álbum en vivo de 1993, Live Seeds, y muestra el sonido agresivo del nuevo grupo.
A mediados de 1993, el grupo regresó una vez más a Londres y grabó Let Love In, el álbum de seguimiento. Let Love In amplió el sonido de conjunto más completo que se había establecido en Henry's Dream y contó con contribuciones de Howard, Ellis, Tex Perkins (Beasts of Bourbon) y David McComb (The Triffids). Varias canciones populares, como “Red Right Hand” (que apareció en la serie de películas Scream) y “Loverman” (más tarde versionada por Metallica), se extrajeron del álbum. Durante la gira promocional del álbum, el percusionista y baterista estadounidense Jim Sclavunos se unió al grupo.

En 1996, la banda lanzó Murder Ballads, su álbum más vendido hasta la fecha. Centrado en el tema del asesinato, el álbum incluye una versión de la canción folclórica “Henry Lee” —un dúo con la cantante de rock británica PJ Harvey, con quien Cave tuvo una breve relación— y “Where the Wild Roses Grow”, un dúo con la ídolo pop australiana Kylie Minogue. La colaboración con Minogue fue un éxito comercial en el Reino Unido y Australia, y ganó tres Australian Recording Industry Association (ARIA) Awards, incluido Canción del Año. Fue en este momento cuando Ellis de Dirty Three comenzó a trabajar regularmente con la banda y finalmente se convirtió en el colaborador principal de Cave.
El sonido de The Boatman's Call, lanzado en 1997, fue un cambio radical con respecto a las narrativas arquetípicas y violentas del pasado de la banda, presentando canciones sobre relaciones, pérdida y anhelo, a menudo con arreglos dispersos. Cave reveló su mentalidad durante la creación del álbum en una entrevista de 2008: "Cuando estaba haciendo la mitad de ese disco estaba furioso porque habían sucedido ciertas cosas en mi vida amorosa que me molestaron seriamente. Y algunas de esas canciones salieron directamente de eso. No me arrepiento de haberlo hecho... las canciones son de un momento en el que te sentías de cierta manera. Cuando... simplemente piensas, '¡Joder, por favor!'" La gira correspondiente del álbum fue documentada más tarde en el álbum en vivo de 2008, Live at the Royal Albert Hall. Después del lanzamiento del álbum, Cave se embarcó en un breve hiatus, tiempo durante el cual se volvió a casar.

Tras el hiatus de Cave, la banda supervisó el lanzamiento de Original Seeds, una compilación de material de otros artistas que influyeron en el grupo, así como su propio álbum de "grandes éxitos" The Best of Nick Cave and The Bad Seeds. El seguimiento propiamente dicho de The Boatman's Call fue No More Shall We Part de 2001. El disco contó con apariciones invitadas de Kate y Anna McGarrigle y fue generalmente bien recibido en las críticas: un crítico aclamó el álbum como un "álbum completo de canciones de amor profundamente trágicas y hermosas sin ironía, sarcasmo o resolución violenta", al tiempo que afirmó que el trabajo corría el riesgo de degenerar "en cursilería".
Luego, la banda lanzó Nocturama en 2003. El álbum marcó un regreso a los arreglos orientados a la banda y colaborativos, ya que los lanzamientos anteriores implicaban un menor nivel de participación de los compañeros de banda de Cave. Nocturama obtuvo críticas mixtas, con el crítico Eric Carr afirmando que "en verdad, aún puede ser el mejor trabajo del grupo desde Let Love In, pero tenía el potencial de ser mucho más". Poco después del lanzamiento del álbum, Bargeld dejó la banda después de 20 años para dedicar más tiempo a Einstürzende Neubauten.
En 2004, la banda lanzó el aclamado set de dos discos Abattoir Blues/The Lyre of Orpheus, con Bargeld reemplazado por el actor, guitarrista y organista inglés James Johnston, miembro de Gallon Drunk y antiguo miembro invitado de The Bad Seeds de una gira de Lollapalooza diez años antes (Johnston solo tocó órganos en las grabaciones, ya que Harvey contribuyó con las partes de guitarra). Concebido como dos álbumes separados empaquetados juntos, el disco presentó una diversidad de estilos de arreglos, incluyendo rock agresivo y baladas impulsadas por coros. En 2005, la banda lanzó B-Sides & Rarities Vol 5, una colección de tres volúmenes y 56 canciones de caras B, rarezas y pistas de compilación que se lanzó en Mute Records en Europa, Estados Unidos y el Reino Unido. The Abattoir Blues Tour, un box set de dos CD y dos DVD con actuaciones de la gira promocional del álbum, se lanzó luego en 2007 en Europa y Estados Unidos. La gira incluyó vocalistas de apoyo invitadas Ase Bergstrom, Geo Onaymake, Eleanor Palmer y Wendi Rose.

También en 2005, Cave completó el trabajo en su guion para The Proposition, un western ambientado en la Australia del siglo XIX dirigido por John Hillcoat, quien también dirigió y coescribió Ghosts of the Civil Dead. Cave y Ellis colaboraron en la banda sonora de la película, una asociación que más tarde también musicalizaría las películas The Assassination of Jesse James by the Coward Robert Ford (2007) y The Road (2009).

Después de operar durante varios años como una banda de acompañamiento de gira para el trabajo en solitario de Cave, los miembros de The Bad Seeds, Ellis, Sclavunos y Casey, formaron un nuevo proyecto paralelo, Grinderman, con Cave en 2006. La banda, con Cave tocando la guitarra por primera vez de forma significativa, tocaba música influenciada por el garage rock que aún conservaba gran parte del aura de The Bad Seeds y lanzó un álbum debut homónimo en 2007. En octubre de 2007, Cave fue incluido en el ARIA Hall of Fame y, en su discurso de aceptación, también incluyó a los miembros de The Bad Seeds y The Birthday Party, después de explicar: "Realmente no puedo aceptar esto hasta que aclaremos algunas cosas. Lo que no puedo entender es por qué estoy aquí y The Bad Seeds no".
Nick Cave and the Bad Seeds lanzaron su 14º álbum de estudio, Dig, Lazarus, Dig!!!, en 2008 y recibió un alto nivel de aclamación crítica. Inspirado en la historia bíblica de la resurrección de Lázaro de Betania por Jesucristo, el álbum continuó con los arreglos inspirados en el punk y el garage rock que se exploraron en el álbum debut de Grinderman, dando como resultado lo que NME denominó un "apocalipsis gótico psico-sexual".

Luego, el grupo se embarcó en una gira por América del Norte y Europa en apoyo del álbum, con una alineación de siete miembros que no incluía a Johnston, quien había dejado el grupo después de la finalización del álbum.

Cave y la banda curaron la primera edición australiana del festival de música All Tomorrow's Parties que se llevó a cabo en varios lugares australianos durante enero de 2009. El 22 de enero, después de la finalización del festival, Harvey anunció su partida de la banda después de 25 años, citando "una variedad de razones personales y profesionales". Harvey concluyó su declaración pública diciendo: "Continuaré trabajando en el proyecto de reediciones del catálogo anterior de The Bad Seeds durante el próximo año y espero con ansias las nuevas oportunidades que podré acomodar como resultado de mis circunstancias cambiantes". La partida de Harvey fue el final de una colaboración musical de 36 años entre Cave y Harvey, y Cave se quedó como el único miembro original del grupo. La banda contrató al guitarrista Ed Kuepper, exmiembro de las bandas australianas The Saints y The Laughing Clowns, como miembro de gira para completar las fechas de los festivales de verano programadas para 2009. También en 2009, Cave publicó su segunda novela The Death of Bunny Munro, y Mute Records comenzó a trabajar en una serie de version y hermosas sin ironía, sarcasmo o resolución violenta", al tiempo que afirmó que el trabajo corría el riesgo de degenerar "en cursilería".

Luego, la banda lanzó Nocturama en 2003. El álbum marcó un regreso a los arreglos orientados a la banda y colaborativos, ya que los lanzamientos anteriores implicaron un menor nivel de participación de los compañeros de banda de Cave. Nocturama obtuvo críticas mixtas, con el crítico Eric Carr afirmando que "en verdad, aún puede ser el mejor trabajo del grupo desde Let Love In, pero tenía el potencial de ser mucho más". Poco después del lanzamiento del álbum, Bargeld dejó la banda después de 20 años para dedicar más tiempo a Einstürzende Neubauten.
En 2004, la banda lanzó el aclamado set de dos discos Abattoir Blues/The Lyre of Orpheus, con Bargeld reemplazado por el actor, guitarrista y organista inglés James Johnston, miembro de Gallon Drunk y antiguo miembro invitado de The Bad Seeds de una gira de Lollapalooza diez años antes (Johnston solo tocó órganos en las grabaciones, ya que Harvey contribuyó con las partes de guitarra). Concebido como dos álbumes separados empaquetados juntos, el disco presentó una diversidad de estilos de arreglos, incluyendo rock agresivo y baladas impulsadas por coros. En 2005, la banda lanzó B-Sides & Rarities Vol 5, una colección de tres volúmenes y 56 canciones de caras B, rarezas y pistas de compilación que se lanzó en Mute Records en Europa, Estados Unidos y el Reino Unido. The Abattoir Blues Tour, un box set de dos CD y dos DVD con actuaciones de la gira promocional del álbum, se lanzó luego en 2007 en Europa y Estados Unidos. La gira incluyó vocalistas de apoyo invitadas Ase Bergstrom, Geo Onaymake, Eleanor Palmer y Wendi Rose.

También en 2005, Cave completó el trabajo en su guion para The Proposition, un western ambientado en la Australia del siglo XIX dirigido por John Hillcoat, quien también dirigió y coescribió Ghosts of the Civil Dead. Cave y Ellis colaboraron en la banda sonora de la película, una asociación que más tarde también musicalizaría las películas The Assassination of Jesse James by the Coward Robert Ford (2007) y The Road (2009).
Tras esta racha de actividad, The Bad Seeds permaneció inactivo mientras Grinderman se reactivó y lanzó Grinderman 2 en 2011. El grupo también atrajo más atención cuando su canción “O Children” apareció en la película de 2010 Harry Potter and the Deathly Hallows – Part 1. En diciembre de 2011, Grinderman se disolvió inmediatamente después de una gira australiana. Su última actuación fue en el Meredith Music Festival en la zona rural de Victoria.

El 15º álbum de estudio de Nick Cave and the Bad Seeds, Push the Sky Away, fue lanzado a mediados de febrero de 2013. Durante la grabación del álbum, el exmiembro Barry Adamson se reincorporó a la banda como bajista. En 2013, Adamson reemplazó a Wydler como baterista de la banda, quien no pudo hacer la gira por razones de salud. Kuepper también regresó como guitarrista de gira de la banda.

En 2014, Cave y Ellis compusieron la banda sonora del largometraje del director francés David Oelhoffen, Loin des Hommes (Far from Men). La banda sonora se publicó un año después, cuando la película tuvo un estreno más amplio. También fue el tema y coescribió el drama documental 20,000 Days on Earth.

A mediados de 2016, se anunció que Cave and the Bad Seeds lanzarían un nuevo álbum en septiembre de 2016, Skeleton Tree. Un documental sobre Cave y la realización de Skeleton Tree, One More Time with Feeling, fue programado para su estreno en cines la misma semana que el álbum. En mayo de 2017, Mute Records lanzó Lovely Creatures: The Best of Nick Cave and the Bad Seeds, un set de tres CD/un DVD que recopilaba los aspectos más destacados de la carrera de Cave desde 1984 hasta 2014. Cave and the Bad Seeds regresaron en 2019 con Ghosteen, un álbum doble que cerró la trilogía del grupo con Push the Sky Away y Skeleton Tree. En 2020, cuando la pandemia de COVID-19 obligó a Cave and the Bad Seeds a cancelar su gira programada, Cave organizó un concierto en una sala vacía, actuando con un repertorio que abarcaba toda su carrera, acompañado únicamente por su propio piano. La actuación fue filmada y grabada, y el álbum Idiot Prayer: Nick Cave Alone at Alexandra Palace fue lanzado en noviembre de 2020. Dos semanas después, Decca Records lanzó L.I.T.A.N.I.E.S., la grabación de estreno de una pieza operística del compositor Nicholas Lens con letras de Cave. En 2021, Cave y Ellis colaboraron en el álbum de estudio nominado al Grammy, Carnage, un set austero y melancólico que se basó en atmósferas cinematográficas y la presencia lírica siempre intensa de Cave. El año siguiente vio la publicación de Faith, Hope, and Carnage, un libro con extensas conversaciones con el periodista Sean O'Hagan. Wild God, el primer álbum con The Bad Seeds en cinco años y un reflejo de un estado emocional más feliz, apareció en 2024.