Поводом к этому стала ретро-вечеринка «Оранжевая Мама», которую устроила в марте 1993 года в ДК имени Ильича на Московском, 152 одноименная продюсерская компания, представлявшая собой семью Натальи и Олега Кушнеревых с радиостанции «Балтика».

В состав новой группы вошли: Андрей «Худой» Васильев (гитара, вокал), Вадим Курылёв (бас-гитара, вокал), Евгений Лёвин (гитара, вокал), Сергей Паращук (вокал, тамбурин), и Михаил Нефёдов (барабаны). В последний момент, буквально за три дня до дебюта, Паращук придумал название по строчке из знаменитой «Песни про зайцев», что было принято сразу под веселый хохот всех участников. Невероятная популярность квинтета оказалась большой неожиданностью.

Весной 1993 года «Дубы-Колдуны» дали ещё несколько концертов, в том числе в клубе «ОсоАвиАхим», где к ним присоединился Николай Гусев («АВИА»), в августе выступили на ночной вечеринке в Манеже. При участии групп «Браво», «Препинаки» и «88 воздушных поцелуев» в сентябре были участниками пароходного круиза «ОсоАвиАхима», а также записали на студии «Indie» свой альбом «Там, за горизонтом» (в роли звукорежиссёра выступил Александр Миронов, Н. Гусев играл на органоле, бас-вокал — Александр Ливер из НОМ). Альбом включал довольно близко к оригиналу перепетые песни из репертуара «Поющих сердец», «Поющих гитар», «Весёлых ребят» и, естественно, «Бременских музыкантов». В конце того же года альбом выпустила на кассетах и компакт-дисках московская независимая компания «Тау-продукт».

В марте 1994 года «Дубы-Колдуны» стали одними их хэдлайнеров первого фестиваля журнала «Rock Fuzz» «АэроFuzz» в Театре «Балтийский Дом», где играли на площадке «Dancing Party».

К этому времени Наталья Кушнерева уехала в Москву, однако, продолжала поддерживать группу и устроила там несколько концертов (ночное выступление в клубе «Sexton Fo.Z.D.»). Кроме того, «Дубы-Колдуны» дали концерт в телецентре на Шаболовке. Он был снят, но так и не вышел на экраны.

В марте-апреле 1995 года музыканты записывали второй альбом «Не повторяется такое никогда?» (названием стала строка из одноименной песни «Самоцветов»). Работа шла на студии «ДДТ» на Тамбовской, в ДК Железнодорожников, за пультом находился продюсер и звукорежиссёр Андрей Муратов. Участвовали гитарист Игорь Романов (экс-«Союз») — он сыграл на соло-гитаре, барабанщик Игорь Доценко (ковбелл), Игорь Тихомиров (безладовый бас), а также Юрий Шевчук, который спел в одном из вариантов песню «Солнце взойдёт», но потом «от своих слов отказался». То есть — передумал. На компакт-диск песня попала, все же, с голосом Курылёва. Однако, успела выйти в свет аудиокассета с шевчуковским, и на некоторые радиостанции также был отправлен сингл. Вот и получилась типичная «аудиоредкость».

Ещё до окончания записи стало ясно, что несомненным хитом нового альбома станет знаменитый «Клён» из репертуара «Синей птицы», поэтому группа и Андрей Муратов решили сопроводить его клипом при участии «всех звёзд». Видео было снято в начале августа 1995 года близ телецентра, на берегу Карповки, а участие в нём приняли Вадим и Глеб Самойловы («Агата Кристи»), Анастасия Полева («Настя»), Вячеслав Бутусов («Наутилус Помпилиус»), Сергей Галанин («СерьГа»), Владимир Шахрин («Чайф») и Олег Гаркуша («АукцЫон»).