В ноябре 1976 года Столярова пригласили уже знаменитые тогда АРГОНАВТЫ, которые в то время исполняли репертуар своего основателя Петра Жукова и клавишника Александра Розенбаума. АРГОНАВТЫ много выступали, были весьма популярны в городе, но избыток собственных авторов на давал Столярову возможности реализовать свой материал, поэтому параллельно он начал репетировать собственные песни в компании старых приятелей и музыкантов АРГОНАВТОВ под именем ВЕЧНОЕ ДВИЖЕНИЕ.
В первый состав группы вошли: Столяров, гитара, вокал; Олег Киселев, бас; Геннадий Лабунский, гитара, вокал; Николай Галактионов, клавишные, и Борис Прокофьев (экс-ФЕНИКС, LOOK AT YOURSELF), барабаны. Этому составу не было суждено выйти на сцену, но следующая версия группы, теперь называвшейся МЫСЛИ И ВРЕМЯ, приняла боевое крещение, сыграв в конференц-зале больницы на Костюшко (где они тогда репетировали) с ВОСКРЕСЕНИЕМ, СОЛНЦЕМ и т. д. На этом этапе за барабанами находился АРГОНАВТ Владимир Калинин, а его коллега по группе Петр Жуков выступил в роли звукооператора.
Тем же составом лето 1978-го группа отыграла в одном из санаториев Адлера, а осенью Столяров окончательно ушел из АРГОНАВТОВ и дал своей группе новое имя ДИЛИЖАНС – по одной из своих песен.
Поскольку остальные АРГОНАВТЫ остались на своих местах, ДИЛИЖАНСУ сразу пришлось заняться комплектацией состава. За следующий год за клавишами в группе промелькнули несколько человек, в т. ч. Николай Кутин и Александр Смолин (экс-ЗЕРКАЛО САНКТ-ПЕТЕРБУРГА), а на пост барабанщика претендовали некий Андрей (фамилия уточняется) и Сергей Соловьев, но стабильности так и не было.
ДИЛИЖАНС в Магадане
Следующее лето они, уже как ДИЛИЖАНС, опять провели на Юге (на клавишных играл Галактионов, а за барабанами чередовались Калинин и Соловьев). В 1980 году редактор питерского ТВ Зоя Иванкович помогла им записать несколько своих номеров. Песня «Дилижанс» даже прозвучала в какой-то телепередаче, но остальной материал так и остался неизданным. На запись в ДИЛИЖАНС был приглашен Сергей Л. Данилов из ДНЯ РОЖДЕНИЯ.
Время от времени они выступали в городе, а когда на горизонте замаячила идея Рок-клуба, стали одной из его первых звезд. (Если быть точным, то в самом процессе организации клуба Федор Столяров и Володя Калинин сыграли ключевые роли, фактически инициировав начало переговоров музыкального андерграунда и властей.) Выступление ДИЛИЖАНСА на мини-фестивале клуба в ДК «Невский» в мае 1981-го стало для группы настоящим триумфом, однако вскоре Столяров и его коллеги поняли, что клуб может помочь начинающим, но бессилен, когда речь идет о проблемах сложившихся музыкантов. В результате после фестиваля ДИЛИЖАНС покинул Рок-клуб и временно лег на дно.
В 1982 году из больницы на Костюшко ДИЛИЖАНС переехал в пригородный ДК «Нива» (в с/х «Шушары») и начал готовиться к переходу на профсцену. Состав группы усилили опытные музыканты: гитарист Сергей Белолипецкий (экс-АРГОНАВТЫ, ГОЛЬФСТРИМ), выпускник Консерватории клавишник Андрей Борейко (ВЕСЕЛЫЕ ГОЛОСА) и барабанщик Игорь Комиссаров (экс-КАРАВЕЛЛА, ПОСТ и т. д.). В июне группа удачно выступила на Днях молодежи в Выборге, однако осенью в ней снова начались разногласия, и Белолипецкий с Борейко ушли. Первый позже собрал ЭЛЕКТРОСТАНДАРТ, а второй возглавил МОДЕЛЬ.
В сезоне 1982/83 года ДИЛИЖАНС регулярно выступал на сцене Дворца Молодежи: его состав пополнил гитарист Василий Горин из СОЮЗА ЛЮБИТЕЛЕЙ МУЗЫКИ РОК, а на клавишных временно играл Олег Скиба из МАНУФАКТУРЫ, пока этот пост в феврале 1983-го не занял еще один ветеран 70-х, Александр «Шура» Алексеев (экс-АЭРОПЛАН, РОССИЯНЕ, ДВЕ РАДУГИ). Группа наконец обрела крепкий в профессиональном отношении состав. Тем не менее все попытки Столярова легализовать ДИЛИЖАНС не имели успеха, и музыканты зарабатывали на жизнь, играя на танцах в Песочном. Устав от полосы неудач, осенью 1983-го группу покинул Лабунский.
В конце 1983 года ДИЛИЖАНС подписал контракт с Магаданской филармонией, став наконец профессиональной группой. Началась типичная концертная рутина: менялись города, концертные площадки, филармонии, появлялись новые песни, приходили и уходили музыканты. Комиссарова в августе 1984-го сменил Андрей Круглов из эстрадных ЗЕМЛЯН, а в начале 1985-го состав усилил его земляк, гитарист Александр Скрябин (тоже из ЗЕМЛЯН, но уже настоящих).
Весной ДИЛИЖАНС подготовил новую программу, которую собирался показать в Питере, но тут распалась группа Олега Гусева (так в то время назывался АВГУСТ), и Гусев пригласил в свой новый состав Круглова со Скрябиным. За барабанами в течение весны и лета 1985 года промелькнули Андрей «Кузнечик» Алексеев (экс-РОССИЯНЕ, МИФЫ, ЗЕЛЕНЫЕ МУРАВЬИ, ДВЕ РАДУГИ), потом опять Комиссаров, к которому осенью прибавился Константин Иванов, начинавший в группах ЗОЛОТОЕ ВРЕМЯ и АРС и игравший на электронных барабанах. Какое-то время в ДИЛИЖАНСЕ было два барабанщика, но потом Комиссаров снова ушел. В этом составе группа устроилась в Астраханскую филармонию.