Lynda Mandolyn una sera approccia Mr. Nancy al Bottom Of The Hill, storico locale di San Francisco dove la stessa Nancy lavora come barista e cassiera, perché indossa la maglietta del gruppo della sua migliore amica. Nancy, che suona il basso nei Fiction, è una grande fan dei Piston, il gruppo in cui suona Lynda, e vorrebbe unirsi a loro: ma non hanno bisogno di un bassista e pertanto Nancy come ripiego chiede a Lynda, Laura Litter e Sally Gess, compagne di band di Lynda, di formare un gruppo tutto al femminile, come sfida, giusto per un concerto. Il gruppo, formato da Laura alla voce, Lynda alla chitarra, Nancy al basso e Sally alla batteria, fa le prime prove nel gennaio del 1998, dandosi qualche tempo dopo, su proposta di Sally, il nome di Fabulous Disaster, prendendo ispirazione da una frase detta da Malcolm McLaren, manager dei Sex Pistols, al riguardo di Sid Vicious nel film "Sid & Nancy". Nel giro di poco tempo le Fabulous Disaster diventano però il progetto principale delle quattro ragazze, e la band inizia a suonare qualche concerto nei dintorni della sua città, San Francisco, California, registrando anche un demo di quattro canzoni. Agli inizi del '99 Cheri Lovedog, ex componente dei Lovedog, si unisce alla band come seconda chitarrista, e con lei le Fabulous Disaster sul finire dello stesso anno si recano al Bottom Of The Hill, che fa utilizzare loro le attrezzature che il locale usa per i concerti live, per registrare un secondo demo, con una spesa piuttosto contenuta, 200 dollari. La band registra 14 canzoni in presa diretta nelle sei ore di un pomeriggio (da mezzogiorno alle sei), ed il risultato è talmente buono che il gruppo decide di farne un rilascio ufficiale: è così che nel dicembre del '99 esce in 1.000 copie "Pretty Killers" (che contiene anche le quattro canzoni del primo demo come bonus tracks, portando il totale a 18), il primo full-length del gruppo, edito dalla Evil Eye Records, etichetta creata da Lynda e suo marito Serge qualche tempo prima. Poco dopo Cherry lascia la band, venendo sostituita dopo qualche tempo con Mia d'Bruzzi, con la quale il gruppo parte per il suo primo tour in Europa, a cavallo tra il maggio ed il giugno del 2000.
Un giorno Nancy dà "Pretty Killers" a Erin, moglie di Fat Mike dei NOFX nonché boss della Pink & Black Records, sottocasa della Fat Wreck Chords (di proprietà dello stesso Fat Mike) specializzata in band con forti componenti femminili. Erin rimane impressionata dal CD, e lo fa sentire anche a suo marito, che è da tempo alla ricerca di un buon gruppo tutto al femminile, da quando aveva assistito qualche anno prima ad un concerto delle Tribe 8 rimanendo impressionato dalla scena punk lesbica californiana. Le Fabulous Disaster sono proprio ciò che da anni sta cercando: ragazze che sappiano suonare veloce ed essere contemporaneamente melodiche, e per di più tre su quattro sono lesbiche (tutte tranne Lynda, sposata). Lui ed Erin vanno così a vedere un loro concerto, e sempre in giugno decidono di concedere loro un contratto, con la Pink & Black, diventando così la seconda band a firmare per la casa (i primi sono stati i Dance Hall Crashers). Presto però anche Mia decide di lasciare il gruppo, facendolo tornare un quartetto. La band nel novembre del 2000 si chiude per undici giorni al Motor Studios di San Francisco per registrare insieme a Fat Mike e Ryan Greene (che ha già lavorato con band quali Lagwagon, Nerf Herder e Dance Hall Crashers oltre che coi NOFX) un nuovo full-length, "Put Out Or Get Out", che esce nel marzo del 2001 (la gamba della foto di copertina è di Sally). La band, che nel frattempo è diventata un'occupazione a tempo pieno per le quattro componenti, parte così prima per un tour negli Stati Uniti con J Church, Avail e Propagandhi, e poi, agli inizi della primavera, per uno in Europa, dove condividono il palco con Mad Caddies e, in Inghilterra, Ataris. Il gruppo gira anche un video per il brano "Minimize My Faith" e nell'estate del 2001 partecipa al Vans Warped Tour, continuando poi a promuovere "Put Out Or Get Out" prima con un tour di tre settimane in Canada di supporto ai Real McKenzies e poi con uno in cui suonano come headliner nel sud degli Stati Uniti, ma è quando nel marzo del 2002 suonano qualche concerto con i NOFX che vengono esposte a delle attenzioni ancora maggiori. In agosto iniziano a registrare demo per il nuovo album, che iniziano ad incidere in ottobre insieme a Alex Newport, già produttore di Sepultura e At The Drive In, tra gli altri, ma sempre con Fat Mike a supervisionare. Intanto il discreto successo che la band sta avendo le ha consentito di esaurire tutte le copie del primo album "Pretty Killers", mentre il nuovo, "Panty Raid!", esce nel febbraio del 2003. Partono così per vari tour, che le vedono anche partecipare all'edizione del Deconstruction Tour di quell'anno, che consente loro di andare per la terza volta in Europa e di suonare insieme a band quali NOFX, Strung Out, Boy Sets Fire e Bouncing Souls, tra le altre. Ma al ritorno negli Stati Uniti, dopo un concerto il 12 giugno a San Francisco, il gruppo annuncia che Laura ha deciso di lasciare le Fabulous Disaster, in termini completamente amichevoli: è una cosa che aveva già comunicato alle altre da qualche tempo, e la decisione è unicamente legata al suo desiderio di non suonare in un gruppo che sta in tour per metà dell'anno.