На дореволюционном плане города она обозначена как улица Железнодорожная. После восстановления в городе Советской власти, а точнее с июня 1920 года, стала именоваться Интернациональной. Нынешнее название — в честь Коммунистического Интернационала — носит с 22 июля 1925 года.
В 20-х годах прошлого вдоль всей улицы стояли бревенчатые срубы. Когда же в октябре 1927 года здесь выросло первое в Мурманске каменное, в три этажа, здание транспортно-потребительского общества (ТПО), оно «представлялось небоскребом». Несмотря на перебои с кирпичом и цементом, стеклом и краской, семьдесят рабочих во главе с прорабом Рассом строили быстро: начали в мае, а через четыре месяца закончили. В здании со стеклянным куполом открылись универмаг и столовая. На фасаде были установлены часы.
Неподалеку от здания ТПО располагались Дом таможни и своего рода гостиница - Дом рыбака и оленевода, а ближе к оврагу - клуб «Местран», принадлежавший работникам местного транспорта - торгового порта и морского агенства. За углом нынешнего здания управления пароходства (начало улицы Профсоюзов) стоял клуб железнодорожников. По другую сторону улицы, против пригорка со зданием ТПО, размещались маленькие домики (общее название - Почтовый поселок) и четыре примечательных объекта: гостиница "Желрыбы" (первая в городе), биржа труда, рынок, стадион железнодорожников.
Гостиница открылась 31 августа 1924 г. Для того времени гостиница была неплохой: двадцать шесть жилых номеров, вместительный ресторан с высоким камином и даже две ванны. Здание, кстати, существует до сих пор, но частично перестроенное (стоит севернее железнодорожного вокзала, вплотную к перрону).
Район нынешнего слияния улиц Коминтерна и Шмидта назывался прежде Красной Горкой. Один из домов на ней занимал Мурманский Совдеп. В конце 20-х годов Красную Горку срыли. В середине 20-х годов на улице находился бревенчатый одноэтажный дом губкома РКП(б).
До 30-х годов улицу пересекали (от нижней террасы к улице Ленинградской) рельсы "декавильки", по которым громыхали дрезины с вагонетками. В ноябре 1934 года, когда в городе открылась первая автобусная линия (Жилстрой - ул. Карла-Либкнехта), одна из остановок 16-местного автобуса ГАЗ-АА появилась и на улице Коминтерна. Перед войной улица являлась крупным общественным и культурным центром города. Здесь находились три клуба, Дом рыбака и оленевода, гостиница, стадион, вокзал, рынок, гастроном ТПО и еще четыре магазина.
Во время войны фашистские летчики активно бомбили железнодорожный узел. Пострадали, естественно, и прилегающие участки города. Большинство домов улицы сгорело. Утром 21 декабря 1941 года бомба весом 250 кг попала в здание ТПО. К счастью, она не взорвалась, а только пробила крышу и междуэтажные перекрытия. Пиротехники вывезли её за город и уничтожили.
Восстановление и реконструкция улицы начались сразу после окончания боевых действий в Заполярье и завершились в основном к середине 60-х годов. Новый вокзал (точнее - его центральный корпус) вступил в строй и принял первых пассажиров накануне Первомая 1954 г. (архитектор А. Мимбаревич). Первоначально здание покрыли терракотовой штукатуркой, но она быстро закоптилась, из-за перепада температур стала отпадать и её пришлось удалить. С тех пор вокзал красят чаще всего в салатный или зеленый цвет.
В 1959 года на куполе здания установили пятнадцатиметровый шпиль со звездой. Операцию всего за четверть часа выполнил экипаж вертолета в составе Г. Строева и В. Кривенко. Крылья - правое и левое - пристроили к центральному корпусу в 1960-1961 гг. Тогда же возникла Привокзальная площадь. На ней были посажены голубые ели и установлен памятник в честь первоходцев космоса (человек, устремленный к звездам). Теперь на площади только полотно асфальта, заставленное автомашинами.
Сегодня улица Коминтерна - своеобразный транспортный узел Мурманска. Кроме железнодорожного вокзала, здесь автовокзал и стоянки автобусов пригородных линий, филиал агенства Аэрофлота, железнодорожные кассы, диспетчерский пункт такси. От привокзальной площади - переход к морскому вокзалу.
Существенных перемен за последнее время не произошло, лишь на стыке с улицей Шмидта снесено несколько старых строений, да претерпело перепланировку здание ТПО: здесь в 1989 году открылся зал художественных выставок, а затем - Художественный музей.
