Историческая дорога на Можайск, Смоленск и другие города на западе от Москвы первоначально проходила от Кремля по современным улицам Воздвиженка, Арбат, Смоленская и Большая Дорогомиловская через Смоленскую площадь, по Дорогомиловскому (позже Бородинскому) мосту, мимо Киевского вокзала до Дорогомиловской заставы Камер-Коллежского вала.
    С созданием в 1742 Дорогомиловской заставы Камер-Коллежского вала были разграничены Дорогомиловская улица и Можайская дорога. В конце XIX века появилось название Можайское шоссе.
    В 1957 году была пробита новая прямая магистраль на запад: место переулков старого Арбата занял широкий Новый Арбат, через Москва-реку был перекинут Новоарбатский мост, из Новодорогомиловской улицы, восточной части Можайского шоссе и улицы Кутузовская слобода был выделен Кутузовский проспект
    Проспект застраивался монументальными сталинскими домами как парадная западная магистраль столицы.
    В 1976—1992 гг. участок Можайского шоссе (от Площади Победы) назывался в память об Андрее Антоновиче Гречко (1903—1976), Маршале Советского Союза, дважды Герое Советского Союза, с 1967 года Министре обороны СССР
    В 1992 году проспект Маршала Гречко включен в состав Кутузовского проспекта.