В 1991 году Крэйг Николлс познакомился с Патриком Мэттьюзом, работая в сиднейском "Макдональдсе". Вкусы парней сошлись на том, что оба тащились по "Нирване". Вскоре они сами стали пробовать свои силы в музыке – Крэйг взялся исполнять роль поющего гитариста, Патрик подыгрывал ему на басухе, а на ударные взяли школьного друга Мэттьюза Дэвида Оллиффа. К тому времени ребята также стали увлекаться британскими командами типа "Suede", "Supergrass" и "Verve". В октябре 1994-го троица отыграла свой первый концерт под вывеской "The Vines" (название команда получила в честь "The Vynes" – группы, которую возглавлял отец Крэйга в 60-е годы). Действо происходило в боулинг-клубе, и парни исполнили всего три песни, каверы "Nirvana" и "You am I".
С тех пор прошло четыре года, а "Vines" все еще довольствовались редкими выступлениями в местных клубах. Удача немного улыбнулась им в конце 1998-го, когда в пабе "The Iron Duke" их впервые вызвали на бис. Время шло, ребята продолжали сочинять песни и раз в неделю ходили в студию готовить демки. Каким-то образом о группе прознали на сиднейском радио "FBI", и в апреле 2000-го музыканты были приглашены туда для интервью, а затем композиция "In the jungle" попала в эфир.
Песню эту случайно услышал Энди Касселл из "Winterman and Goldstein Management" и "Ivy League Music". Запись его очень впечатлила, и он связался с группой. Вместе со своими партнерами Питером Ласти и Энди Келли Касселл занялся профессиональным менеджментом "Vines". Под их руководством были подготовлены демки всех песен. Пленки разослали в несколько рекорд-компаний, и те немедленно проявили интерес к творчеству группы. В сентябре 2000-го в рамках культурной программы Олимпиады команда отыграла целый сет, а уже в октябре впервые появилась на крупной площадке, выступив на разогреве "You am I". Крэйг на сцене вошел в раж, порвав на себе рубашку и начав было крушить свою гитару, чем вызвал дополнительный интерес у лейблов.
В конце 2000-го музыканты со своими менеджерами обсуждали вопрос о выборе компании и, в конце концов, остановились на молодой сиднейской фирме "Engine room". В феврале 2001-го "The Vines" приступили к подготовке дебютного альбома, тщательно переработав свои демки ("Drown the Baptists," "Get Free," "Winning Days," "Mary Jane," "Outtathaway," "Sunchilld") с австралийским продюсером Грегом Уэльсом.
После небольшого национального тура в компании все с теми же "You am I" группа улетела в Лос-Анджелес заканчивать сессии. В сентябре из-за недостатка бюджета работа была приостановлена, а тем временем команду покинул Оллифф. Сессии возобновились в ноябре и были завершены с помощью барабанщиков Джоя Варонкера и Пита Томаса. Вышедший в том же месяце дебютный сингл "Factory" подстегнул интерес лейблов и вскоре у "Vines" на руках было еще два контракта (с американской "Capitol" и английской "Heavenly"). По возвращению в Сидней группа отыскала себе нового ударника, которым стал Хамиш Россер, а затем обзавелась и вторым гитаристом по имени Райан Гриффитс.
После нескольких выступлений на родине "The vines" отправились в Англию, где буквально поставили на уши британцев. Группа была приглашена в передачу "Top of the pops", а ее сингл занял в Британии 32-е место. Последовавшее североамериканское турне прошло с аншлагами. Но самый главный успех ожидал группу с выходом в свет альбома "Highly evolved". С ним "The vines" стали первой австралийской бандой, дебютировавшей в британских чартах в первой пятерке (третье место). Чего уж говорить об Австралии, где музыканты были признаны национальными героями и их хедлайнерские выступления неизменно сопровождались аншлагом.