С начала 2001 года BILLY DILLY’S BAND начали выбираться с концертами в клубы: «Fish Fabrique», «Лайзу», «Пороховую бочку» и т. д. Весной 2001 года они сыграли в программе «English Day» на сцене «Зоопарка». Тогда же в «Boom Brazza» гостила группа туристов из Германии, которая в порядке ответного жеста доброй воли пригласила всю команду клуба – включая BILLY DILLY’S BAND – в гости. Решив, что поездка должна иметь практическую цель, группа немного обновила программу, опробовала ее в т. н. Холодной Трубе, после чего месяц колесила по Германии, дав серию концертов в Берлине и Мюнхене, причем играла как в местных клубах, так и просто на улице. Именно тогда Билли решил сменить гитару на контрабас (позднее он играл на инструменте, ранее принадлежавшем Владимиру Волкову из ВОЛКОВТРИО) и не без оснований считает, что настоящая история группы начинается именно с этого момента.
Перед самым отъездом Максимачев (звукорежиссер как по образованию, так и по призванию) записал в «Зоопарке» девятнадцать номеров, которые, по сути дела, стали дебютным альбомом BILLY DILLY’S BAND «Игры в Tom Waits» (или «Being Tom Waits»). Осенью 2001 года у группы появился директор – лидер рэггей-группы С.О.К. Максим Новый, стараниями которого она значительно расширила ареал своего существования – сначала за счет респектабельных питерских залов (типа ирландского паба «Mollie’s»), а затем и московских клубов «Китайский летчик Джао Да», «Бункер», «Ритм-энд-блюз», «Проект О.Г.И.» и т. п. Следом пришло время более театральных площадок: «Бродячая собака», «Приют комедианта», «Чаплин», что заставило группу задуматься о театрализации своих концертов. (Параллельно Новик, Резников и Матезиус аккомпанировали своему директору в составе группы С.О.К.)
С активизацией концертной жизни группу покинули оба перкуссиониста, а сама она решила сменить название – со слегка легкомысленного BILLY DILLY’S BAND на более строгое BILLY’S BAND. Неудивительно, что к Новику с этих пор накрепко приклеилось сценическое имя Билли.
В марте 2002 года BILLY’S BAND нанесли свой второй визит в Германию. Ему тоже предшествовала запись в «Зоопарке», правда, на этот раз были записаны и собственные песни Билли, составившие авторский альбом «Немного смерти, немного любви».
В мае BILLY’S BAND выступили на II этапе питерского рок-фестиваля «Окна Открой!» в клубе «Полигон» и, очаровав жюри, без труда пробились на гала-концерт, который состоялся 23 июня на Крестовском острове. В конце июля BILLY’S BAND отправились в свою третью поездку по Германии, а осенью 2002-го совершили небольшое турне по Франции и Голландии.
По возвращении из турне, оказавшегося во всех отношениях успешным (после него в репертуаре группы появилось множество новых песен), BILLY’S BAND засели в студии, чтобы реализовать свежий материал. Новый альбом получил название «Парижские сезоны» (с прозрачной отсылкой к другим россиянам, имевшим художественный успех в столице моды). К записи было привлечено еще несколько музыкантов, в частности пианист Александр Буткеев (р. 18.11.71 в Нижнем Новгороде), который большую часть 90-х гастролировал по стране с вокальным джазовым квартетом ДАЙДЖЕСТ, бас-гитарист Сергей Вырвич (MAD LORI, С.О.К.), скрипач Максим Жупиков (AD LIBITUM, SHERWOOD), тромбонист Василий Савин (р. 5.01.76 в Ленинграде) (ЛЕНИНГРАД, ЧИРВОНЦЫ), барабанщик Евгений Бобров (р. 15.07.66 в Ленинграде) (O.S.A., СПОКОЙНОЙ НОЧИ, BIG BLUES REVIVAL), а звукорежиссером вновь стал Дмитрий Максимачев.
Декабрь 2002 года был отмечен двумя значительными событиями: 7-го группа отметила (естественно, в клубе «Red Club») пятьдесят третий день рождения Тома Уэйтса, а 19-го дебютировала на сцене БКЗ «Октябрьский», приняв участие в питерской премьере новой программы Гарика Сукачева и НЕПРИКАСАЕМЫХ «Полюби меня».
Презентация «Парижских сезонов», которые стали первым официальным альбомом BILLY’S BAND (он вышел с буклетом, новым логотипом группы и т. п.), прошла 24 января 2003 года все в том же «Реде». На его сцене был впервые представлен расширенный состав группы, BILLY’S BIG BAND, в который – помимо основного трио – вошли Савин, Бобров, Жупиков и Максимачев (перкуссия).
1 апреля Билли Новик спел вместе с лидером БАОБАБОВ Настей Постниковой в их праздничной программе «Первоапрельская оргия». Любопытно, что в тот же день открылся официальный сайт BILLY’S BAND. Той же весной вся группа приняла участие в записи альбома Оркестра ЗАЧЕМ «Волшебная страна 03» и начала работу над своим новым диском. В процессе записи в ряды BILLY’S BIG BAND органично влился опытный музыкант – саксофонист Михаил Жидких (р. 23.09.65 в Городце Ростовской обл.), который аккомпанировал на сцене и работал в студии с десятками исполнителей самых разных жанров – от эстрады и попсы до тяжелого рока, включая Максима Леонидова, Альберта Асадуллина, Петра Подгородецкого, ОТПЕТЫХ МОШЕНИКОВ, PUSHKING, СТИНГЕР Сергея Боярского и т. д. Жупиков между тем ушел, чтобы возродить группу фолк-барокко SHERWOOD.