La Dave Matthews Band nasce nel 1991 a Charlottesville, in Virginia, precisamente al Miller's Bar, il luogo che rappresenta il cuore pulsante della scena musicale di quegli anni e dove Dave Matthews, che li lavora come barista, incontrerà una serie di personaggi e musicisti, molti dei quali ricompariranno spesso durante la storia della band negli anni a venire. Fra questi Greg Howard, John D'Earth, Tim Reynolds, LeRoi Moore e Carter Beauford.
Nel Novembre del 1990, con l'aiuto di Greg Howard e su sollecitazione di Ross Hoffman, Dave Matthews ha già registrato una prima demo contenente The song that Jane likes, I'll back you up, Recently e The best of what's around. Il batterista Carter Beauford ed il sassofonista LeRoi Moore sono già musicisti affermati nella scena jazz di Charlottesville e l'allora sconosciuto Dave chiede loro di aiutarlo a registrare una demo. Inizialmente riluttanti al progetto, entrambi accettano dopo avere ascoltato il suo nastro. Nasce cosi il nucleo originario della band, composto da Dave Matthews (voce e chitarra), Carter Beauford (batteria) e LeRoi Moore (sassofono).
Le prime prove, a casa di Carter e della madre di Dave, sono disastrose: la band non ingrana, nessuno riesce a trovare il giusto approccio ai brani ed è come se al trio mancasse equilibrio. Poco tempo dopo, uno dei musicisti più popolari della scena di Charlottesville, il trombettista John D´Earth, si esibisce al Miller's con una jazz band di studenti: fra di loro, spicca l´appena sedicenne Stefan Lessard, al quale viene ben presto proposto di suonare il basso elettrico con la nuova, improvvisata session-band.
Stefan si rivela la chiave di volta, la musica di Matthews ne guadagna in energia e compiutezza, gli stessi musicisti ne sono entusiasti. Al momento di registrare Tripping billies, tuttavia, Dave ritiene di avere bisogno di un violino e spunta fuori il nome di Boyd Tinsley, già celebre, nella scena di Charlottesville, grazie ai suoi due gruppi, Down Boy Down e Boyd Tinsley Band. In occasione di un suo concerto al Miller's, quindi, Dave lo contatta per chiedergli aiuto, e Boyd accetta: in fondo è solo per una registrazione.
Nessuno lo sa ancora, ma in quel momento nasce una leggenda.
Nella prima demo realizzata in studio dalla Dave Matthews Band vengono incise "The song that Jane likes", "Recently" e "Tripping Billies". Il gruppo è ancora ufficialmente formato da Dave, Leroi, Stefan e Carter. Boyd dà solo il suo contributo, in qualità di guest, nella registrazione di "Tripping Billies".
La scelta del nome avviene quasi per caso: è LeRoi Moore a suggerire al proprietario di un club, dove la band si deve esibire, di scrivere solo il nome "Dave Matthews". Ma il gestore ritiene che non sia corretto e scrive "Dave Matthews Band". L´esibizione ha successo e il gruppo rimarrà legato a quel nome improvvisato.
Il 20 Aprile 1991 la band suona per la prima volta, dal vivo e gratis, a Charlottesville. Boyd Tinsley vi compare come guest, in quanto ancora legato ai suoi precedenti progetti musicali. Questo concerto è noto come l'Earth Day show, che tuttavia si festeggia il 22 Aprile, ma anche le note di copertina del Greatest Hit Volume 1 confermano e suggellano il 20 Aprile 1991 come una data storica per la DMB. L'11 Maggio 1991 un'amica della band, Lydia Condor, li invita a suonare ad una festa al Pink Warehouse, luogo che darà successivamente il nome a "Warehouse" una delle song più ispirate mai uscite dal talento di Dave Matthews.
La nuova band inizia ad esibirsi sempre più spesso dal vivo, ottenendo un discreto successo. Ma i tempi sono duri ed i primi ingaggi non bastano certo a far tornare i conti alla fine del mese: in effetti, fino al 1992, le performance live della band non vengono nemmeno pagate. In compenso, la vena creativa di Matthews è in costante fermento e le poche canzoni iniziali si moltiplicano in breve tempo, affiancandosi a un repertorio di cover come "Angel from Montgomery" di John Prine o "The maker" di Daniel Lanois, tutte rivisitate in chiave estremamente personale.
Una delle personalità che maggiormente influenzano la band in questo periodo è, senza dubbio, quella di Haines Fullerton. Fullerton, insieme a Mark Roebuck, ha alle sue spalle l'esperienza con la band The Deal ed entrambi collaboreranno anche alla composizione di due brani della DMB: Fullerton per "#34", Roebuck per "The song that Jane likes".
Nei primi anni 90, Haines Fullerton è conosciuto come un semplice barista, personaggio umile e gentile, ma anche complesso, affascinante e con uno straordinario talento musicale. Haines ha certamente avuto, in quegli anni, una grossa influenza sullo stile chitarristico di Dave. Così lo definisce il musicista-deejay-giornalista David Wellbeloved: "È quasi mistico. Non puoi sederti con lui e non diventare un musicista diverso. La sua influenza la puoi sentire in ognuno di quelli che hanno suonato almeno una volta con lui". A sua volta, Haines è affascinato da Dave. È uno dei primi a cogliere l'essenza più intima della sua musica, ad assorbirne la poesia: delle sue canzoni riesce a spiegare ogni sfumatura, ogni singola parola e parla di lui come di un ragazzo con un sicuro avvenire.