Árið 1991 byrjaði The Vines fyrst að myndast þegar að Craig Nicholls hitti Patrick Matthews. Craig hafði klárað 10 bekk og ákveðið að byrja í listaskóla af einhverju tagi. Til að fjármagna þetta nám vann hann á McDonalds og hitti þar Patrick fyrst. Á þessum tíma höfðu þeir báðir mjög gaman af Nirvana og það var kannski það sem að leiddi þá saman í fyrstu. Þeir byrjuðu að spila saman bara tveir, Craig á gítar og Patrick á bassa og seinna bættist trommarinn David Oliffe við, en hann var vinur Patrick. Craig borgaði fyrir tíma fyrir þá í stúdíói, Craig söng og spilaði ásamt félögum sínum og þegar að þeir heyrðu útkomu þessa stúdíó tíma ákváðu þeir að þetta væri það sem að þeir vildu gera og hættu þeir í vinnum sínum og snéru sér alfarið að tónlist.
Árið 1994 spiluðu þeir félagar á sínum fyrstu tónleikum undir nafninu The Vines en hugmyndin var sprottin frá hljómsveit sem að faðir Craigs var í en hét hún The Vynes. Þeir héldu áfram að spila saman og æfa og senda “demo” til fólks sem að gæti haft áhuga. Fólkið, að minnsta kosti eitthvað af því, hafði áhuga og fengu þeir félagar að spila á tónleikum á einu kvöldi ólempíuleikanna í Sydney árið 2000.
The Vines komust á samning hjá Engine Room (sem að var þá frekar nýtt plötufyrirtæki) og hófu að taka upp fyrstu smáskífur sínar (innihéldu þær til dæmis lögin Get Free, Mary Jane, Outtathaway, Sunchild, Winning Days og Drown the Baptists) og voru skífurnar gefnar út í Ástralíu árið 2001. Um sumarið sama ár var hringt í þá frá Sunset Studio's Schnapf og buðust þeir til að gefa efni þeirra út í Bandaríkjunum. Í kjölfar þessarar hringingar flugu þeir til Los Angeles.Þeir byrjuðu að taka upp efni en eitthvað voru peningarnir ekki nægir þannig að smá pásu þurfti að gera á öllu saman David Oliffe fannst miklir hlutir vera að gerast of hratt svo hann ákvað að hætta í sveitinni.
Vegna klúðrinu sem að átti sér stað hjá Sunset Studio's Schnapf ákvaðu The Vines að gera frekar samning við Capitol Records í Bandaríkjunum og Heavenly Records í Bretlandi. Vegna þess að Oliffe hafði hætt í bandinu vantaði þá náttúrulega trommara og þess vegna bættist Hamish Rosser við hljómsveitina, og stuttu síðar kom líka æskuvinur Craigs Ryan Griffiths, í hljómsveitina og átti hann að vera “aðstoðar” gítarleikari. Saman spiluðu þeir inn á breiðskífu sem að hlaut nafnið Higly Envolved og kom hún út í júlí 2002.