El grupo se formó en 1993 cuando Melanie Blatt y Shaznay Lewis se juntaron para comienzar a grabar y escribir en un estudio de la calle All Saints Road, en el Ladbroke Grove de Londres. El dúo fue fichado por la vocalista de R&B Simone Rainford y editó un solo single para ZTT Records en 1995, pero Rainford dejó el sello y prescindieron de las chicas. Pero la derrota no pudo con ellas y Blatt & Lewis alistaron a la canadiense Nicole Appleton y después a su hermana mayor Nathalie en las filas del grupo, que pasaría a ser un cuarteto llamado All Saints.

Con la ayuda de un amigo del grupo, Karl Gordon (anteriormente componente del grupo de rap Outlaw Posse), All Saints graban una maqueta con el tema "I Know Where It's At". Un nuevo manager, John Benson, decide representar a las chicas, firmando con London Records que las puso en contacto con los superproductores Nellee Hooper (Massive Attack, Björk) y Cameron McVey (Neneh Cherry). Graban "I Know Where It's At" con el que golpean con fuerza las listas británicas, llegando incluso a Europa y Asia. En 1997 All Saints alcanzan el número uno de las listas con el tema de su segundo sencillo "Never Ever". El cuarteto edita su álbum homónimo, que marcaría su debut en Lp en noviembre de 1997, comenzando a oirse en EE.UU. y entrando en el top ten de las listas americanas con "I Know Where It's At".

De sus temas se realizan varios mixes y remixes que vieron la luz como "Maximum All Saints" y "Remixes Album", pero para la confirmación de las All Saints como grandes artistas habría que esperar hasta el 2000, año en el que editan su segundo trabajo de estudio titulado Saints & Sinners.

En 2006 publican nuevo material Studio 1.