A Vasteras, in Svezia, alla fine del 1995, nasce un gruppo: la line-up è formata da Mårten Cedergran alla voce, Sami e Richard Andersson alle chitarre, Mathias "Mini" Lindh al basso e Chrille alla batteria. Inizialmente la band si chiama Down And Out, ma presto cambia nome in Bombshell Rocks. Nel febbraio del '96 registrano un promo da sei canzoni, che spediscono a varie label svedesi, senza però che nessuna si interessi a loro, decidendo perciò di autoprodursi. Dopo qualche mese però Chrille decide di uscire dalla band per impegnarsi maggiormente nel suo hobby, lo skateboard, venendo presto rimpiazzato da un vecchio amico del gruppo, Thomas Falk. Nel febbraio del '97 esce così (un anno dopo la sua registrazione), autoprodotto (l'edizione viene accreditata alla loro label Nincompoop), il singolo "Who's The Real Bastard?". In estate iniziano così a suonare in giro, salvo interrompere per qualche girono alla fine di agosto per registrare un EP di tre tracce, prima che in dicembre Sami decida di lasciare il gruppo, presto rimpiazzato con Christian "Crippe" Määttä. La band effettua lo stesso mese il suo primo mini tour (della durata di una settimana), prima di essere contattata, nel febbraio del '98, dalla Sidekicks Records, una sotto-casa della Burning Heart Records. Il lavoro registrato nell'agosto precedente esce qualche mese dopo, nella primavera del '98, con il nome di "Going Up And Going Down", per la casa discografica creata da Mårten e Thomas, la Noiseline Records. A cavallo tra maggio e giugno incidono, in quattro giorni, al Sound Lab Studio di Örebro, sempre in Svezia (di proprietà di Mathias Färm dei MIllencolin), l'EP, edito dalla Sidekicks, "Underground Radio", contenente 6 canzoni, che ottiene notevoli lodi e che porta il gruppo ad entrare nuovamente nello studio del cantante dei Millencolin, nel novembre del '98, per registrare il suo full-length d'esordio, "Street Art Gallery". Il giorno dopo la fine delle incisioni Richard lascia la band perché non vuole andare in tour, e viene sostituito da Ola Hjelmberg. "Street Art Gallery" esce sempre su Sidekicks, mentre negli U.S.A. viene pubblicato dalla Epitaph. Il tour di promozione dell'album segna 150 date, nelle quali suonano con 59 Times The Pain, Liberator, No Fun At All, Voice Of A Generation e Dropkick Murphy's, venendo in seguito messi sotto contratto direttamente dalla Burning Heart Records. Nell'estate del 2000 entrano nuovamente nel Sound Lab Studio per registrare, per la Burning Heart, "Cityrats & Alleycats", avvalendosi della collaborazione, tra gli altri, di Mathias Färm dei Millencolin.