Летом 1972 года Макаревича и Кутикова пригласили влиться в состав легендарного ансамбля «Лучшие годы», в котором играли такие знаменитые музыканты, как барабанщик Юрий Фокин (экс-«Скомо-рохи»), клавишник Игорь Сеульский и вокалист Сергей Грачев, почитавшийся у нас тогда за «двух Томов Джонсов или за полтора Элвиса Пресли». В течение года «Машина Времени» выступает с собственной программой внутри концерта «Лучших годов». Именно тогда широкая московская публика впервые обратила внимание на группу Макаревича, так как она стала петь на русском языке. Особым успехом пользовались песни «Продавец счастья», «Солдат» и «Очки с розовым стеклом». Но несмотря на актуальность текстов и музыки, «Машина Времени» в московском рейтинге групп, поющих на русском языке, занимает в то время только третье место вслед за Градским и «Оловянными Солдатиками», а затем — за «Цветами» Стаса Намина.
За полтора года, с осени 1973 по 1975 годы состав «Машины» неоднократно менялся, в группе приняло участие около 15 музыкантов, среди них — Алексей Романов, барабанщики Юрий Фокин и Михаил Соколов, гитаристы Алексей «Вайт» Белов («Удачное приобретение») и Александр Микоян («Блики»), скрипач Сергей Осташев и др. «Лучшие годы» оставили в «Машине» свой след в виде клавишника Игоря Саульского, который, впрочем, неоднократно уходил ради выступлений в составе «Арсенала», «Аракса» или «Скоморохов» Градского, но всегда возвращался. В 1973 году в результате разногласий с Кавагоэ Кутиков уходит в «Високосное Лето». На басу некоторое время играл Макаревич, а на гитаре — Игорь Дегтяркж («Второе дыхание»).
В 1974 году имя «Машины Времени» впервые появилось на пластинке фирмы «Мелодия», когда группу попросили помочь в записи музыканты из Трио Линник («Зодиак»), исполнявшего американский фолк. Маленькая пластиночка состояла из двух песен Вадима Линника на русском языке и песни Боба Дилана «Грузовой поезд». Эта пластинка в дальнейшем не раз выручала ансамбль в борьбе с чиновничьим произволом.
В 1975 году наконец-то стабилизировался состав группы: Андрей Макаревич (гитара, вокал), Сергей Кавагоэ (барабаны), Евгений Маргулис (бас-гитара, вокал). В марте 1976 года «Машина Времени» с успехом выступила на «Днях популярной музыки» в Таллине, после чего по приглашению группы «Аквариум» дала несколько концертов в Ленинграде. И это стало началом массовой «машино-мании» в городе на Неве и признания группы в Москве «Машина Времени» теперь гастролирует в Питере каждые 2–3 месяца и с неизменным аншлагом, на некоторое время в группу перешел лидер питерской команды «Мифы» Юрий Ильченко (гитара). Росту популярности «Машины Времени» способствовал и эпизод в фильме Г. Данелия «Афоня». в котором звучит песня «Солнечный Остров».
Без сомнения, конец 70-х является пиком творчества «Машины Времени» Именно тогда были написаны такие хиты, как «Пока горит свеча». «Хрустальный город», «Кого ты хотел удивить?» Макаревич сумел лучше, чем кто бы то ни было, выразить настроения нашей молодежи, сформулировать мучившие ее вопросы: как вернуть мир на путь правды? Как вырваться из липких лап застоя? Большинство песен было написано в виде аллегорических притч, они берут свое начало в творчестве Булата Окуджавы и даже — баснописца прошлого века И. А. Крылова. Эзопов язык песен Макаревича на многие годы определил стиль московской школы рока.
Что же касается музыки, то первые опыты «Машины Времени» были основаны на мелодике «Битлз», в середине 70-х пришла пора хард-рока и белого блюза, а конец десятилетия был отмечен влиянием джаз-рока, когда после ухода Ильченко в 1977 году в группе появились саксофонист Евгений Легусов, трубач Сергей Велицкий (его год спустя заменил трубач Сергей Кузьминок), клавишник Александр Воронов (экс-«Виктория») и вновь вернувшийся Игорь Саульский. В 1978 году группа подготовила и реализовала грандиозный замысел — литературно-музыкальную композицию «Маленький принц», где в паузах между тематически подобранными песнями читал стихи поэт Александр «Фагот» Бутузов.
Но летом 1979 года в результате внутренних противоречий группу покинули Е. Маргулис и С. Кавагоэ, вместе со старыми друзьями — Алексеем Романовым, Алексеем Макаревичем и Андреем Сапуновым — они организовали группу «Воскресенье». А. Воронов вернулся в «Викторию». Но примерно в то же самое время «Високосное Лето» реорганизуется в «Автограф» и А. Кутиков возвращается в «Машину Времени», захватив с собой барабанщика Валерия Ефремова. Четвертым участником группы стал молодой пианист Петр Подгородецкий. В таком составе «Машина времени» сначала поступила в Московский Областной Театр Комедии, а вскоре перешла на службу в Росконцерт.