Мытнинская улица проходит от стыка 2-й Советской улицы и проспекта Бакунина до улицы Моисеенко. Первое её название – Болотная – известно с 1828 года. Между этой улицей и Невой располагалось обширное болото, почти до конца XIX века остававшееся незастроенным. По нему получили свои имена соседние Большая и Малая Болотные улицы.

Болотная улица (Мытнинская) и Мытный Двор на плане Петербурга 1828 года (фрагмент).

Первая из них сейчас называется улицей Моисеенко, вторая разделена на улицы Бонч-Бруевича и Красного Текстильщика. В отличие от Большой и Малой Болотных, просто Болотная сохраняла своё наименование недолго. Уже в 1836 году появилось название Мытнинская улица. Здесь начиная с 1730-х годов был Мытный двор, современный его адрес – проспект Бакунина, 6. Существующее сейчас здание построено в 1785 году и впоследствии неоднократно перестраивалось.

В середине XIX века параллельно существовали ещё несколько имён: Большая Болотная; просто Большая; Рожественская улица, поскольку местность эта в ту пору называлась Рожественской слободой, а современные Советские улицы – 1-10-й Рожественскими, а слово «Рожественский» писалось без буквы «д»; и, наконец, Малый проспект. Большим и Средним проспектами в последнем случае считались Слоновья (ныне Суворовский проспект) и Дегтярная улицы.