До 1663 года Пенза представляла собой деревянный острог с небольшим посадом. В мае 1663 года в Пензу по приказу царя прибыл архитектор Ю.Е. Контранский. Под его руководством было начато строительство города — крепости. 

Архитектурная концепция старой крепости, возведенной на восточном склоне надречной горы, предопределила направление первых улиц. Направление и местоположение первых улиц задавались проездными башнями крепости и ориентировкой ее стен. Так сложились первые пять улиц города. Самые «старые» улицы Пензы: Богданова (Пешая), Лекарская (Володарского), Московская, Никольская (Карла Маркса), Замойского (Пушкарская), Кирова (Троицкая).

Улица Пешая была одной из самых старых улиц Пензы. Своё название она получила от слободы пеших казаков пензенского крепостного гарнизона, которые в XVII веке, во времена основания города, получили здесь земельные наделы и подворья. В 1939 году улица получила современное название в честь русского советского писателя-революционера Александра Алексеевича Богданова.