Dave Smalley, ex membro di DYS, Dag Nasty ed All, dopo avere abbandonato questi ultimi, si accorge che non riesce a stare senza fare musica e, avendo già scritto alcune nuove canzoni che gli piacciono molto, pensa di creare una nuova band: nel 1990 inizia così a suonare a Los Angeles, California, con il suo amico Dave Nazworthy detto "Naz" alla batteria, già membro dei Chemical People. In breve si uniscono a loro altri due membri dei Chemical People, Ed Urlik al basso e Jamie Pina alla chitarra. La formazione è ora completa, e la band si dà nome Down By Law, prendendo ispirazione dall'omonimo film di Jim Jarmusch: alla band piace molto questo appellativo perché è anche un'espressione usata molto dai neri per dire che sono d'accordo con una cosa, ed ha anche l'idea di andare contro la legge, in perfetto stile punk.
Il gruppo inizia a suonare qualche concerto qua e là, ma rimanendo un side-project, dato che Dave Smalley è ancora alle prese con la sua laurea in Scienze Politiche (suo padre è tra l'altro stato ambasciatore nell'era Reagan) e tutti gli altri tre reputano i Chemical People di primaria importanza: ma presto comunque i Down By Law arrivano alle conoscenze di Brett Gurewitz, chitarrista dei Bad Religion e proprietario della Epitaph, che già conosce Smalley per via delle sue precedenti band e che presto decide di entrare con loro al West Beach Recorders di Hollywood, California (lo studio che Brett condivide insieme a Donnell Cameron), per produrgli il loro primo album. Al termine delle incisioni, quando l'album è ancora in fase di mixaggio, Jamie lascia però la band, immediatamente sostituito da Chris Bagarozzi dei Clawhammer: quando l'album, omonimo, esce, nell'aprile del '91, la band quindi già non è più composta dalla sua formazione originale. La band parte comunque per un tour di promozione che li vede suonare anche in Europa, e l'anno successivo torna al West Beach per registrare il suo secondo album, "Blue", prodotto da Brett e Donnell, che esce sempre per Epitaph nel'ottobre del '92.
Ma in seguito Urlik, Nazworthy e Bagarozzi decidono di andarsene, lasciando unico membro originario Smalley, il quale in breve recluta però Mark Phillips alla chitarra, Pat Hoed (un amico di Nazworthy e membro anche dei Brujeria) al basso e, per un tour, Colin Sears, ex Dag Nasty insieme allo stesso Smalley, alla batteria, il quale viene però presto sostituito da Hunter Oswald, un ragazzo che vive in Florida: con la nuova formazione si reca così nel febbraio del 1993 al Surrogate Spike Studios di Los Angeles per registrare dei brani per un doppio EP in edizione limitata, "D.C. Guns", che esce lo stesso anno per la Selfless Records. In luglio esce anche per la Lost & Found Rercords uno split da tre canzoni ciascuno con i Gigantor (in cui due dei tre brani dei Down By Law sono suonati da Dave Nazworthy), poi ristampato dalla Break Even Point Records l'anno successivo sottoforma di un EP contenente solo i tre brani dei Down By Law intitolato "Yellow Rat Bastard".
Nel frattempo avvengono nuovi sconvolgimenti nella line-up: prima se ne va Mark, sostituito da Sam Williams III (anche lui residente in Florida, a Tampa), e poi anche Pat, rimpiazzato con "Angry" John DiMambro. Questa formazione si reca così all'A&M Studios di Hollywood per registrare un nuovo album, proprio mentre di fianco a loro, in un'altra stanza, stanno incidendo anche i Rolling Stones: la prima sera di incisioni, mentre i Down By Law stanno registrando un brano, "Punk As Fuck", ricevono nel loro studio una chiamata dai Rolling Stones che gli chiedono di abbassare il volume perché non riescono a sentire ciò che loro stanno registrando! In questo album i Down By Law dimostrano di essere ormai una band a tutti gli effetti e non più solo Dave Smalley con altri musicisti: se il primo album era stato infatti completamente scritto da lui, già nel secondo era stato aiutato in qualche pezzo e qualche canzone intera, mentre ora Hunter ha scritto da solo quasi metà dell'album. Il lavoro che ne esce è il terzo full-length, "Punkrockacademyfightsong", rilasciato nel giugno del '94 ancora dalla Epitaph, con aspetto grafico curato da Caroline Smalley, moglie di Dave; ma in seguito anche Hunter se ne va, e viene rimpiazzato con Danny Westman.
Sempre nel '94 la Vagrant Records rilascia un box set intitolato "West X North-South" contenente cinque split EP da un brano per gruppo, tra cui anche uno tra Down By Law e Face To Face (gli altri sono tra J Church e Fluf, Alcohol Funnycar e Treepeople, Seaweed e The Meices, e Samiam e Tilt), che viene poi ri-rilasciato l'anno successivo sottoforma di CD.
Nell'estate del '95 i Down By Law tornano all'A&M Studios per registrare un nuovo full-length, partendo subito dopo per la prima volta per le Hawaii, dove suonano ad Honolulu davanti ad una folla di 7.000 persone. Altri tour seguono, e nel marzo del '96 esce ancora edito dalla Epitaph il nuovo album, "All Scratched Up!", la cui versione in vinile, un doppio, contiene un intero lato di bonus tracks (che contiene anche quello inserito nello split con i Face To Face) non incluse nella versione in CD. In maggio partecipano al famoso festival Dynamo Open Air di Eindhoven, in Olanda, dove suonano davanti a 110.000 persone e con tanti gruppi famosi (Slayer e Exploited su tutti), e poi in estate al Vans Warped Tour, mentre nel frattempo il video per "Radio Ragga" girato dalla band viene passato con una certa regolarità anche da MTV: il secondo invece, filmato per "Independence Day", viene mandato in onda meno di frequente, essendo il brano meno commerciale, ma con il suo minuto e 15 secondi di durata diventa comunque il più corto ad essere mai stato passato da MTV.
Ma il problema di reperire un batterista stabile per i Down By Law continua: in seguito infatti anche Danny li lascia, costringendoli ad incidere un nuovo full-length con Chris Lagerborg dei Joykiller, che però non si unisce in via definitiva a loro: l'album, registrato al Sound City di Van Nuys ed al Media Vortex di Burbank, entrambi in California, per la prima volta vede Smalley partecipare come produttore, anche se non da solo. Per le prime date dopo le registrazioni (che li vedono suonare anche in Europa) li aiuta Hunter Oswald, finché non viene trovato grazie ad un annuncio un nuovo batterista stabile, Milo Todesco, che entra a fare parte dei Down By Law nella primavera del '97. La band partecipa poi nuovamente al Warped, ed in luglio gira un video per "Question Marks & Periods", un brano estratto dal nuovo album, "Last Of The Sharpshooters", che esce in agosto sempre per Epitaph. Ma l'album non vende bene come i precedenti due, che avevano raggiunto entrambi le 100.000 copie, fermandosi a quota 60.000: nel '98 la Epitaph decide quindi di scaricarli, ed anche "Angry" John decide di lasciare la band, che però come al solito non si perde d'animo e rimedia al primo problema firmando un contratto per un album con la Go Kart Records di New York, ed al secondo trovando Keith Davies. Con lui si chiudono nel febbraio e marzo del '99 all'Inner Ear Studios di Arlington, in Virginia, per registrare insieme a Don Zientara (già produttore dei Fugazi), coadiuvato da Smalley, un nuovo album, "Fly The Flag", che esce in agosto e vende più o meno come il precedente.
Nel novembre del 2000 la Theologian Records rilascia invece uno split tra Down By Law e Pseudo Heroes, side-project di Sam Williams, contenente brani registrati dal vivo durante la tourneé europea del '99. Nell'aprile del 2002 è la volta della prima raccolta dei Down By Law, "Punkrockdays - The Best Of DBL", edita dalla Epitaph, che contiene anche un inedito (una cover) ed una traccia ROM con due video ("Hit Or Miss" e "Radio Ragga"). La band continua i tour, suonando anche al Full Force Festival con i Motorhead, per poi tornare in studio, questa volta al Gl di Tampa, Florida, ed al Spoondog Studios di Silver Springs, Maryland, per incidere un nuovo full-length, prodotto in parte questa volta da Sam Williams. Il risultato, "Windwardtidesandwaywardsails", esce nel maggio del 2003 per Union 2112 Records, sottocasa della Union Label Group.