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