Cuando debutaron a principios de los 90, All Saints formaban parte de la popular ola de grupos de chicas británicos que iniciaron las Spice Girls. Mientras que las Spice Girls se centraban en el «girl power» y la imagen de sus integrantes, las All Saints eran aficionadas a la música con una imagen más suave y sofisticada, menos ligada a su apariencia y más a su música.

El grupo se formó en 1993 cuando Melanie Blatt y Shaznay Lewis comenzaron a grabar y componer en un estudio ubicado en All Saints Road, en Ladbroke Grove, Londres. El dúo se unió a la vocalista de R&B Simone Rainford y lanzó un sencillo con ZTT Records en 1995, antes de separarse de Rainford y de que el sello las dejara de lado. Sin desanimarse, Blatt y Lewis reclutaron a la canadiense Nicole Appleton y, más tarde, a su hermana mayor, Natalie, para convertir a All Saints en un cuarteto.

Con la ayuda de su amigo Karl Gordon (exmiembro del grupo británico de rap Outlaw Posse), All Saints grabó una demo de la canción «I Know Where It’s At». Su nuevo representante, John Benson, firmó a las chicas con London Records y las puso en contacto con productores de primer nivel como Nellee Hooper (Massive Attack, Björk) y Cameron McVey (Neneh Cherry). Una vez terminada, «I Know Where It's At» alcanzó el puesto número cuatro en las listas británicas y tuvo éxito en toda Europa y Asia.

Para 1997, All Saints había alcanzado el primer lugar con su segundo sencillo, «Never Ever». El cuarteto lanzó su álbum debut homónimo en noviembre de 1997 y comenzó a ganar popularidad también en Estados Unidos, entrando al Top 40 con «I Know Where It’s At». Para 1998, All Saints había obtenido la certificación de platino en EE. UU. y cinco veces platino en el Reino Unido, pero comenzaron a surgir rumores de una separación en el grupo. Blatt esperaba su primer hijo con Stuart Zender, de Jamiroquai, y los chismes afirmaban que iba a dejar All Saints. También se rumoreaba que Appleton había abandonado la banda después de que el grupo no se presentara a la celebración de los ganadores de la encuesta Smash Hits de ese año.

A principios de 2000, su sencillo «Pure Shores», producido por William Orbit, fue incluido en la banda sonora de la película de Leonardo DiCaprio, La playa. Innumerables presentaciones en festivales por todo el Reino Unido también reafirmaron la perdurabilidad de All Saints a pesar de su inestable dinámica. El tan esperado segundo álbum, Saints & Sinners, salió finalmente a la venta en octubre de 2000, lo que impulsó al segundo sencillo, «Black Coffee», a las listas de éxitos, pero los problemas aún se cernían en el horizonte. A principios de 2001, se cancelaron las giras por Japón y Australia. Los celos parecían ser la causa, ya que Lewis y Blatt no veían con buenos ojos el estatus de celebridad de las hermanas Appleton, especialmente la relación de Natalie con Liam Howlett, de The Prodigy, y la de Nicole con el vocalista de Oasis, Liam Gallagher. En febrero de 2001, la separación se hizo oficial. Blatt lanzó su primer sencillo, «Twentyfourseven», en el verano, y Shaznay Lewis estaba componiendo con el productor de All Saints, K Gee. Las Appleton estaban grabando material y haciendo planes para un libro en el que lo contarían todo. All Hits, una recopilación de grandes éxitos de sencillos y un DVD de edición limitada, salió a la venta en el otoño de 2001, lo que aparentemente marcó un amargo final para All Saints.

En enero de 2006, se dio a conocer que el cuarteto se había reunido y había firmado con Parlophone. El primer sencillo de All Saints en más de cinco años, «Rock Steady», salió a la venta en noviembre de ese año y alcanzó el tercer lugar en la lista de sencillos del Reino Unido. El tercer álbum de estudio de la banda, Studio 1, salió a la venta apenas unos días después y debutó en el puesto 40 en el Reino Unido. Al año siguiente, las integrantes se separaron de Parlophone y cancelaron otra gira que tenían planeada. Para alimentar los rumores de otra separación, en septiembre de 2010 salió a la venta la recopilación Pure Shores: The Very Best of All Saints.

Tras cuatro años de silencio, surgieron noticias de una nueva reunión cuando la banda anunció planes para una breve gira en 2014 como teloneras de los Backstreet Boys, así como para presentarse en festivales. Con renovadas energías, planearon discretamente un regreso completo un par de años más tarde. Sin dejar de mostrar su estilo refinado de dance-pop, el sencillo «One Strike» salió a la venta en febrero de 2016. Escrito y grabado sin la participación de un sello discográfico, el álbum completo Red Flag se lanzó en abril. La banda se embarcó en una gira nacional más tarde ese otoño para promocionar el álbum, con un repertorio que incluía viejos éxitos y material nuevo. También volvieron a la carretera a principios de 2017 para ser teloneras de Take That en su gira por estadios. Ese mismo año, All Saints regresó al estudio para comenzar a componer y grabar su quinto álbum. El álbum, titulado Testament, salió a la venta en el verano de 2018.

El 14 de abril de 2020, el grupo lanzó una versión de «Message in a Bottle» junto a Sting. El 20 de abril de 2020 se estrenó un «video oficial de estudio». La banda fue invitada especial durante tres noches en la gira The Wild Dreams Tour de Westlife en 2022. Esta fue la última vez que el grupo se presentó junto tras su pausa indefinida.

Recientemente, las chicas celebraron el 25.º aniversario de su primer álbum, «All Saints», y lanzaron su álbum debut en vinilo por primera vez en el Día Nacional del Álbum en 2024.