Проспект було сформовано шляхом об'єднання ряду вулиць, що існували раніше:
Совської[1] (виникла близько 1897 року, від сучасної Деміївської площі до району Майкопської вулиці),
1-ї Софіївської (виникла у 2 половині 1930-х років, від Дачної вулиці (Олександра Пироговського) до тупика поблизу Народної вулиці, 1965 року була об'єднана з Червонозоряною вулицею[2]),
Червонозоряної (виникла у 2-й половині 1940-х років, від сучасної Севастопольської площі до Дачної вулиці, до 1953 року — 481-ша Нова вулиця[3]),
Семена Палія (виникла у 1950-х роках, від Народної вулиці до Совських ставків, до 1958 року — Ново-Крутогорна вулиця[4]).
1974 року на базі цих вулиць і ще ряду старих проїздів було сформовано єдину магістраль, яка отримала назву Червонозоряний проспект[5].
Є частиною Малої окружної дороги Києва. 2004 року було проведено реконструкцію проспекту, внаслідок чого було ліквідовано більшість світлофорів, збудовано 4 підземні переходи та прокладено нову тролейбусну лінію (до того з 1963 року до 25 травня2004 року існував автобусний маршрут № 17).
Уранці 26 лютого 2022 року одна з ракет РФ влучила в 25-типоверховий житловий будинок № 6-А на рівні 18-го — 21-го поверхів, що призвело до поранення кількох мешканців та зруйнування квартир на цих поверхах.[7]
Більша частина забудови проспекту — одноповерхова та приватна. В середній частині проспекту знаходяться Совські ставки — унікальне заповідне урочище в центральній частині міста зі збереженою екосистемою, являє собою великі заболочені луки зі ставками, очеретовими зарослями та вербами.
У кінцевій частині проспекту збереглася 1-2 поверхова забудова кінця XIX — початку XX століття. Зокрема, збереглася будівля школи, в якій навчався Валерій Лобановський(будинок № 148), у честь якого названо проспект.