Nel 1996 due ragazzi di Novara compagni di classe al Liceo Classico, Diego Cattaneo e Gabriele Musica, alla voce e chitarra il primo ed alla batteria il secondo, iniziano a provare in uno scantinato per divertimento, eseguendo covers di gruppi come i NOFX. Ai due nel 1997 si unisce alla seconda chitarra Roberto Casesi, reclutato attraverso un annuncio, mentre il primo bassista della band è Bruno, che però rimane nel gruppo, che nel frattempo si è dato nome Boldoz Dogs, solo poche settimane. Lo sostituisce Alessandro Duma, con il quale la band inizia a comporre i primi pezzi propri ed effettua il suo primo concerto, il 17 luglio del '97, ad una gara per gruppi rock del novarese, esibendosi insieme a bands già localmente affermate ed eseguendo covers di NOFX e Rancid. In novembre, dopo essersi esibita in diversi rock pub del novarese e vercellese, la band vede allontanarsi per problemi personali Alessandro, il cui posto viene preso poco dopo da Andrea Pigni, un ragazzo conosciuto perché spesso presente ai loro concerti. A questo punto il gruppo inizia a scrivere brani propri in modo serio, i cui testi nel frattempo sono passati dall'italiano all'inglese: nel giugno del '98 il quartetto registra in 13 ore una prima demo-tape omonima di quattro tracce, che viene distribuita sempre indipendentemente nel gennaio del '99, mentre intanto incrementano le esibizioni dal vivo, che portano la band a suonare in zone sempre più lontane. In settembre il demo viene ristampato, mentre dei nuovi brani vengono composti e registrati in due sessioni di studio durante l'arco di un anno allo studio La Grenouille di Palazzolo Vercellese, in provincia di Vercelli: questi vanno poi a comporre, insieme a due pezzi del demo, il primo album del gruppo, "Pataboom", che esce nel 2001 per la Sottosopra Records. Ma i Boldoz Dogs non si trovano soddisfatti con tale etichetta e visto che il contratto è limitato alla prima stampa del lavoro, decidono di affidarsi alla Dave Records per la ristampa, che arriva nei negozi sempre nel 2001. Nel frattempo però si sono create tensioni all'interno del gruppo, che portano all'allontanamento di Gabriele e Andrea, sostituiti rispettivamente da Claude e Hierro: con loro i Boldoz Dogs registrano al La Grenouille nel gennaio del 2002 le basi musicali per due brani, le cui voci vengono poi registrate a luglio al One Voice Studio di Chivasso, in provincia di Torino. I due pezzi sono intesi per uno split con i Marysun!Nicotina completamente scaricabile gratuitamente (compreso l'artwork) dai siti internet delle rispettive bands: lo split, intitolato "Digital Split", viene reso disponibile a partire dal novembre del 2002 e nel primo giorno di uscita viene scaricato complessivamente da 150 persone, continuando al ritmo di una decina al giorno per i primi mesi. Agli inizi del 2003 i quattro registrano allo studio Sonichome di Cavaglio D'Ag. (provincia di Novara) delle canzoni per un secondo full-length, "Since Year One", che esce edito in collaborazione da Dave Records e Kimera Records in maggio.