В 1975 году из «Машины Времени» в группу «Високосное лето» ушёл Александр Кутиков, его место занял басист Евгений Маргулис. Через четыре года, говоря спортивным языком, произошла обратная замена — Кутиков вернулся в группу, а Маргулис вместе с Сергеем Кавагоэ занялись созданием группы «Воскресенье». Вместе с Кутиковым к группе присоединились клавишник и вокалист Пётр Подгородецкий и Валерий Ефремов.
С лета 1979 года начинается самый благополучный за советское время период в истории «Машины Времени». Незадолго до этого на речевой студии ГИТИСа известный в музыкальных кругах звукорежиссёр Андрей Тропилло записал первый магнитоальбом «Машины Времени», позже получивший название «День рождения». Тогда музыканты делали запись, по сути, нелегально, работая по ночам. Но в 1980 году с «нелегальным положением» на какое-то время покончено — «Машина Времени» выходит из подполья и становится первой в СССР официально признанной рок-группой. Ещё в 1979 году музыканты оформляются на работу в Московский областной театр комедии, а через год группа «Машина Времени» переходит в состав «Росконцерта» и в трудовых книжках «машинистов» появляется запись: «Концертная организация „Росконцерт“, артист». Создаётся новая концертная программа, в которую входят такие известные песни, как «Поворот», «Право», «Ах, что за луна», «Снег», «Свеча», «Будет день», «Три окна». Группа отправляется в первое большое гастрольное турне по стране, концерты, на которых нет ни одного свободного места, проходят в Ростове-на-Дону, Харькове, Одессе и других городах. В марте 1980 года «Машина Времени» завоёвывает первое место на тбилисском рок-фестивале «Весенние ритмы-80», а Андрей Макаревич за тексты песен «Снег» и «Хрустальный город» получает специальную премию Союза журналистов СССР. Песня «Снег» появилась и на пластинке «С Новым 1980 годом!», выпущенной фирмой «Мелодия», а песня «Поворот» 18 месяцев занимала верхние строки в первом советском хит-параде, публиковавшемся в газете «Московский комсомолец».
Всё это благополучие закончилось в 1982 году. В США на студни «Kismet Records» выходит диск «Машины Времени». С одной стороны, событие приятное, несмотря даже на то что диск фактически пиратский и сами музыканты до момента его выхода ничего не знали. «Мы удивлены. Поражены. Вознесены в собственных глазах», — вспоминали «машинисты». Но тут же следует реакция властей: «Имеем неприятную беседу с сотрудником Органов Внутренней Секреции». А затем в «Комсомольской правде» появляется «Рагу из синей птицы» — письмо, подписанное группой видных жителей Сибири, якобы возмущённых прошедшими в Красноярске концертами «Машины Времени».
Со времени опубликованной в 1936 году в «Правде» статьи «Сумбур вместо музыки», в которой уничтожающей критике было подвергнуто творчество Дмитрия Шостаковича, «Рагу из синей птицы» стала самой громкой статьёй в советской прессе, посвящённой музыкальной тематике. Собственно говоря, в самом факте появления такого письма нет ничего страшного и предосудительного. Ну не понравилось некоторым жителям Красноярска выступление московской группы «Машина Времени», они об этом написали в центральную газету, и газета это письмо опубликовала. Кстати, первым в списке подписавшихся была фамилия известного писателя-фронтовика Виктора Астафьева, человека, отношения которого с властью и цензурой тоже складывались не всегда гладко. Так что думается (хотя вряд ли можно утверждать об этом со стопроцентной уверенностью), что письмо в «Комсомольскую правду» не было «заказным». Хуже было другое. «Рагу из синей птицы» стало сигналом для многочисленных чиновников от искусства: «Ату их!». Каждое выступление музыканты должны были теперь согласовывать с бесконечными худсоветами, некоторое время «Машине Времени» вообще запрещали выходить на сцену. О пластинках и выступлениях на радио и телевидении можно было забыть. Неудивительно, что когда Андрея Макаревича спрашивают об отношении к советской власти, он до предела категоричен: «Я ненавижу эту власть во всех её проявлениях».
Гонения на «Машину Времени» прекратились после прихода к власти М. С. Горбачёва. Фирма «Мелодия» в 1986 году выпустила первую большую пластинку группы «В добрый час», «Машина Времени» одной из первых советских рок-групп отправилась на зарубежные гастроли.