Улица Коммунистическая появилась на свет вместе с городом, тогда еще Новониколаевском. Только раньше, до 1920 года, она носила имя одного из видных государственных деятелей царской России 19 века Павла Константиновича Гудимы-Левковича и называлась Гудимовской. Генерал-лейтенант П.К. Гудима-Левкович получил образование во Владимирском киевском кадетском и втором военном Константиновским училище. В 1877 году попал в действующую армию, а уже в 1878 году принимал участие в Турецкой военной кампании, исполняя должность начальника штаба 2-ой Гвардейской кавалерийской дивизии. С 1881 года профессор Гудима-Левкович преподавал военное искусство в Николаевской академии Генерального штаба. В 1884 году Павла Константиновича назначили помощником начальника штаба войск и Петербургского военного округа. Чуть позже он стал управляющим кабинетом Его Императорского Величества Александра III, членом коронационной комиссии и членом Государственного Совета. Именно Павел Гудима-Левкович обучал военной тактике последнего российского Императора Николая II. Летом 1895 года управляющий Кабинетом Его Императорского Величества П.К. Гудима-Левкович проезжал через поселок и выразил начальнику Алтайского округа Болдыреву пожелание назвать растущее поселение в честь царя – Николаевским. Болдырев передал пожелание Томскому губернатору и начальнику строительства Среднесибирского участка железной дороги Н.П. Меженинову. 3 декабря 1895 года на сходе жителей поселок было решено переименовать из Александровского и Новониколаевский. Память об этом событии хранили улицы Гудимовская и Болдыревская (Октябрьская).
В 20-е годы улица Гудимовская получила новое название – Коммунистическая. И хоть историческое имя улицы утеряно, дома ее хранят для нас прошлое города.

Это купеческие дома П.М. Зайдана (45) и Ефремова (41), купчихи Жернаковой (43), дом под часами и стадион «Динамо». Наверное, многих удивляет, что стадион стоит под углом к улице Коммунистической. Это объясняется тем, что еще 70 лет назад здание «Динамо» было прозорливо поставлено архитектором Б.А. Гордеевым на предполагаемую в перспективе Вокзальную магистраль: в конце 20-х годов уже высказывались предположения о прокладке широкой улицы, соединяющей вокзал с Закаменским (Октябрьским) районом. Кстати, одним из разработчиков проекта стадиона был инженер Н.В. Никитин, в последующем автор знаменитой башни в Останкино. В одном из старинных особняков конца 19 века по улице Гудимовская (ныне – Коммунистическая, 48) располагался купеческий гостиный двор. Оставив лошадей в конюшне напротив, купцы коротали здесь вечера. История Гудимовской улицы связана и с гостиницей «Метрополитен». Это здание стоит чуть в стороне, по улице Революции (бывшая Дворцовая), дом 4. Если верить городской мифологии, гостиница была обыкновенным «веселым домом», в который любило заглядывать местное купечество. Посетители, боясь ревнивых жен, покидали это заведение по подземному ходу, вырытому в огород в соседнем квартале на Гудимовской. Говорят, что в 1973 году при прокладке кабеля связисты наткнулись на ход, стены которого были облицованы кирпичом. К сожалению, к тому времени свод тоннеля уже обвалился. Вероятно, этот легендарный «черный ход» можно считать первым подземным переходом города.