1975 год. Романов покидает группу, а летом неожиданно уходит и Кутиков, причем не куда-нибудь, а в Тульскую государственную филармонию. В это же время в группе появляется Евгений Маргулис, а чуть позже скрипач Коля Ларин.

1976 год. "Машину Времени" приглашают в Таллин на фестиваль "Таллиннские песни молодежи-76", где они с блеском выступают, и где впервые встречаются с Борисом Гребенщиковым и группой "Аквариум", бывшей в то время милым акустическим квартетом. Гребенщиков приглашает их в Питер. Их концерты имеют бешенную популярность. Скрипача Коли Ларина в составе уже не нет, и его место занимает некто Сережа Осташев, тоже долго не задержавшийся. В это же время к группе присоединяется Юра Ильиченко, солист "Мифов".

1977 год. Ильиченко, стосковавшийся по родному городу, уезжает в Питер, и "Машина Времени" ненадолго остается втроем. И тут Андрею приходит в голову ввести в состав группы духовиков. Так в группе появляется духовая секция: Евгений Легусов и Сергей Велицкий.

1978 год. В составе происходит замена. Вместо Велицкого в команду приходит Сергей Кузьминок. В этом же году происходит первая студийная запись "Машины Времени". Кутиков, игравший к тому времени в "Високосном лете", устроился на работу в учебную речевую студию ГИТИСа, дабы использовать студию по назначению. Андрей Макаревич обращается к нему, Кутиков обещает все устроить, и через несколько дней начинается запись, известная нам как "Это было так давно...". Длилась она целую неделю, и в нее вошли почти все (на тот момент) песни "Машины Времени", за исключением первых ранних. Запись получилась отличная, и уже через месяц звучала повсюду. Жаль, что оригинал ее утерян, а то, что мы сегодня слушаем, копия, случайно оказавшаяся у одного из знакомых Андрея. Осенью "Машина Времени" рассталась с дудками, и в группу вошел синтезатор в лице Саши Воронова, правда, ненадолго.

1979 год. В группе происходит развал. Сергей Кавагое и Евгений Маргулис уходят в "Воскресение". В это же время в группу возвращается Кутиков, который приводит с собой Ефремова, а чуть позже в состав вливается Петя Подгородецкий. "Машина Времени" начинает репетировать в новом составе, и репертуар группы пополняется такими вещами, как "Свеча", "Кого ты хотел удивить", "Хрустальный город", "Поворот". В этом же году "Машина Времени" становится группой Московского гастрольного театра комедии при Росконцерте.