Старт КАФЕ был стремительным и ярким (хотя ему предшествовала долгая подготовка): первая же записанная группой песня стала едва ли не главным хитом года, за ней последовали гастроли по стране, телевизионные эфиры, пристальное внимание массмедиа, два вышедших с интервалом всего четыре месяца альбома, полные интересного материала… Увы, неудачное стечение обстоятельств, чехарда с менеджментом, не вовремя заключенный контракт и человеческий фактор так и не позволили группе закрепить успех.

КАФЕ родилось внутри первой питерской кантри-группы FINESTREET, которая начала свое существование весной 1989 года и к середине 90-х добилась в своем жанре статуса безусловных звезд, но при этом исчерпала резервы развития, оказавшись перед выбором: эмигрировать в Европу или до конца своих дней играть по ресторанам.

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

Так выяснилось, что у Смирнова имеется ворох песен, написанных в русле классических традиций: рок-н-роллы, блюзы, баллады. При этом их отличал несомненный мелодизм и гармоническая ясность потенциальных хитов. Лидер FINESTREET Сергей Стародубцев предложил Смирнову записать альбом, хотя у них на тот момент даже не было группы: остальные музыканты приглашались только на платные выступления.

Стартовым капиталом послужила отданная за долги старенькая «Volvo»: они продали ее за десять тысяч долларов и на студии областного радио «Гардарика» во Всеволожске записали первые десять песен. Стародубцев сыграл на мандолине и гитаре, Смирнов записал часть гитар, бас и вокал, за барабаны был приглашен Арсен Израилов (экс-ПОРУЧИК РЖЕВСКИЙ, НАТЕ! БУРАТИНО-БЭНД), а скрипичные партии исполнил Сергей Мосолов (КУКУРУЗА). Он же ощутимо помог безымянной группе со звуком, став фактически сопродюсером записи.

После этого их пригласили на фестиваль «Инкубатор», который проходил в несколько этапов (один из них состоялся в клубе «Перевал») под патронажем 22-го телеканала. На каждом этапе группа исполняла новые песни. Тогда же она наконец нашла себе имя КАФЕ. В финале конкурса, который состоялся весной 1996-го, КАФЕ обошло С.Т.Д.К. (исполнявших там «Вот лето пролетело») с песней «Давай забудем все, что было».

За победу в «Инкубаторе» КАФЕ получило право записаться на студии и снять клип, который обещал крутить местный канал NBN. За восемь часов группа записала и свела свой первый хит «Товарищ сержант», который попал на радио и вскоре зажил собственной жизнью. На этом этапе группе помогали Анна Кузьмина (бас) и Андрей Бриженюк (барабаны). Той же весной оба расстались с КАФЕ (Кузьмина позднее играла в АРХИВАРИУСЕ и ПИРОТЕХНИКЕ, а Бриженюк в УЛЫБНИСЬ и KAKTUZZ), а новую ритм-секцию группы составили Андрей Косогоров (MANCHESTER), бас, и уже знакомый им Израилов, барабаны.

В 1996 году КАФЕ выступило живьем на студии «Добролет», после чего его судьбой заинтересовался работавший там экс-директор АКВАРИУМА Михаил Гольд. С его подачи внимание на потенциальных хитмэйкеров обратила московская компания «Союз». Она финансировала запись альбома на том же «Добролете» и взялась за его продвижение. «Товарищ сержант» звучал на волнах каждой русскоязычной станции в стране, спрос на группу рос как на дрожжах, и она начала гастролировать. Предваряя альбом, «Союз» издал сингл с «Сержантом» и «Дальней дорогой».

И тут история повторилась. Как FINESTREET, чтобы двигаться дальше, надо было перебираться в Европу, так и КАФЕ ждали в Москве, однако музыканты не спешили паковать чемоданы, а в августе 1998-го в России грянул кризис, и музыкальный бизнес пережил коллапс. Косогоров ушел к НАСТЕ, а позже играл с WINE и различными кавер-бэндами. Его место занял старый приятель всех музыкантов КАФЕ Дмитрий «Дуче» Бациев (р. 15.06.65 в Ленинграде), ак. бас, вокал. В разное время он играл в группах UNDERGROUND, НАТЕ! БУРАТИНО, HOODOO VOODOO и др.

Лишь с приходом 1999 года жизнь начала возвращаться в свою колею. В марте состоялась премьера второго клипа КАФЕ «Фенька (порвалась)». Тогда же Гольд добился для группы нового контракта с «Квадро-Диском», который в августе выпустил альбом «Музыка крыш» на кассетах и компакт-дисках. Его презентация прошла в клубе «Сайгон». Альбому предшествовал выход кассетного сингла. Между тем КАФЕ рвалось в бой и к тому времени уже записало второй альбом. Он тоже вышел под лэйблом «Квадро-Диска», назывался «+12» (по одной из новых песен группы; кроме того, именно столько номеров он добавил в репертуар КАФЕ) и был презентован в декабре в «Лондон-клубе».

К сожалению, момент был упущен: в эфире появились новые хиты, к тому же морально не готовый к интенсивной работе Леша Смирнов пропускал концерты или выступал на них не лучшим образом, что пагубно отражалось на климате в группе. Гольд расстался с ними и уехал в Москву, а делами КАФЕ какое-то время занимался экс-клавишник БУРАТИНО Игорь Александр.

Стародубцев с марта 1999 года параллельно играл в акустическом блюз-бэнде BIG BLUES REVIVAL, а в апреле следующего года стал сооснователем еще одной своеобразной блюзовой группы O.S.A., которая дебютировала в июне 2000 года на фестивале «Анимализм» в клубе «Зоопарк». В обеих в разное время принимал участие и Бациев. Израилов зарабатывал на жизнь в цыганской поп-группе КАБРИОЛЕТ.