Улица, носящая в настоящее время имя Кутякова, образовалась в начале XIX века. В 1818 году купец Крючков на собственные средства построил на Хлебной площади небольшую Сретенскую церковь, которую также называли церковью Петра и Павла. Вокруг храма сразу появились торговые ряды, за которыми уже через несколько лет стала застраиваться улица, названная Петропавловской. К концу XIX века улица Петропавловская доходила почти до полотна железной дороги. Население, строившее дома на этой улице, было, как говорится, пестрым. Очень много домов на Петропавловской улице занимали цыгане, селившиеся здесь целыми таборами. И вскоре улицу переименовали в Цыганскую. Однако нецыганское население бывшей Петропавловской было крайне возмущено такой несправедливостью, и в 1909 году жители обратились в городскую управу с просьбой о переименовании Цыганской улицы в Петропавловскую. Но, к их огорчению, это ходатайство было отклонено, и улица осталась под названием Цыганская. В 1957 году Цыганская улица была переименована в улицу Кутякова — героя гражданской войны, ближайшего соратника и помощника В.И. Чапаева.