Вулицю проклали згідно з генеральним планом забудови Проскурова 1824 року. Спершу вулиця була частиною бульвару, який слугував межею міста. Після розширення міста у 1880-х роках вулиця отримує назву — Старобульварна.
На плані Проскурова 1907 року вулиця починається в районі цегельного заводу та старого кладовища (зараз перехрестя вулиць Завадського та Героїв Маріуполя) та пролягає до русла річки Південний Буг біля єврейського кладовища (зараз перехрестя вулиць Вайсера та Свободи).
У другій половині 1920-х років вулицю розділили на три частини — Старобульварна (зараз вулиця Героїв Маріуполя), провулок Медведівський (зараз вулиця Європейська) та вулицю Дзержинського (зараз вулиця Свободи).
Більше цікавих та маловідомих фактів про Хмельницький у рубриці «Цікаві факти».