À sa création, le groupe est composé d'une chanteuse, Joey Nine, d'une bassiste, Ida Evileye, d'une guitariste, Klara Force, et d'une batteuse, Nicki Wicked. Leur catégorie musicale appartient alors au registre punk rock. Durant les années 90, alors qu'elles ont 14 ans, Ida et Klara jouent pour la première fois ensemble. Nicki, quant à elle, joue dans un groupe de hard rock. C'est en 2001, après l'arrivée de Mia Karlsson, seconde guitariste du groupe qu'elles signent leur premier contrat avec Warner/Chapel Scandinavia à la suite d'un concert donné au rock club sur un bateau en Suède. Elles trouvent leur nom de groupe au Roskilde Festival grâce à une poupée gonflable (barbara en suédois) perchée sur une croix. Toutefois, le départ de Joey Nine, remet le groupe à un nombre pair. Mia s'essaye donc au chant en 2003. Suite au départ de Joey, le quartet féminin, au lieu de mettre un terme au groupe décide de continuer la musique. L'arrivée de Mia dans le groupe change beaucoup le son ; le punk rock laisse une place plus ample au metal.