Вулиця Плеханова в часи Катеринослава називалася Стародворянской. У одній з найстаріших вулиць міста незвичайна історія.
Як розповідають історики, Стародворянская (Дворянська) вулиця так називається через стани, яке там жило. Однією з перших була побудована садиба Євдокії Василівни Синельниковой, дружини намісника краю з 1785 по 1789 рр.. генерал-майора В. М. Синельникова. У 1829 р. вона заповідала будинок Духовному відомству, а в 1840-х роках будівлі розібрали. Починаючись від вул. Йорданській (Коцюбинського), Дворянська слугувала продовженням вул. Ламаної і сама тривала вул. Петербурзької (Ленінградської). Прямий змички цих вулиць не було – вони сходилися під кутом на Обережної площі (нині тут розташований Оперний театр).
На вулиці. Плеханова збереглося кілька будинків катеринославської пори: одноповерхові особняки №8, 9, двоповерхові №1а, 3, 5, триповерхові №4, 6.
Колись на Дворянській розташовувалася важлива для міста служба – Вільна Поштова станція. Відкрита в 1797 р. на 4 коні, вона утримувалася за рахунок населення з податком на 30 коп. з душі. Сюди прибували пошта, фельдъегерские карети, диліжанси, тут міняли коней.
Ул. Дворянська вливалася в Острожную площа, на якій стояли присадкуваті тюремні каземати. У 1896 р. на західній стороні Обережної площі збудовано будинок Аудиторії народних читань (архітектори Л. А. Бродницький і С. Ю. Харманский). Після того, як тут були організовані несанкціоновані міською владою вечори, присвячені пам’яті Т. Г. Шевченка, 1902 р. наказом катеринославського губернатора Комісія народних читань була ліквідована, а будівля передана науковому товариству, утвореному в 1901 р.