Вскоре все предварительные работы были выполнены и началось возведение подсобных помещений, расчистка причальной площади и постройка первого деревянного причала-ряжа размером 21,12х12,4 м, высотой 15,9 м, соединенного с берегом дамбой. В 1933 г. для площадки порта было заготовлено около 100 тысяч м3 скального грунта, две тысячи штук бревен. Все работы проводились практически вручную, почти при полном отсутствии механизмов. Даже многотонный ряж был опущен в воду без тракторов и лебедок. Одновременно прокладывали дорогу от будущего порта. Спустя 11 месяцев причальная площадка охватывала территорию в 20 тысяч м.
6 декабря 1933 г. к ещё не достроенному причалу пришвартовался пароход «Уэлен» (именно эту дату считают официальным днем рождения порта). Окончательное строительство первого причала было завершено 4 июня 1934 г.
Через два года порт получил официальный статус: постановление Совнаркома СССР от 29 июня 1936 г. определило: «Считать Нагаево (Охотское море) портом III разряда, возложив административное управление указанным портом на дирекцию гостреста «Дальстрой». Обязать НКвод СССР включить порт в список портов СССР». Первым начальником морского транспорта Дальстроя, который одновременно исполнял обязанности начальника порта, был Э.О. Лапин (впоследствии репрессированный).
Уже в 1937 г. нагаевцы перегрузили для нужд территории свыше 350 тысяч тонн грузов разного назначения: технику, материалы, продовольствие – всё, в чем нуждалась Колыма. Морем прибыли первые самолёты магаданской авиации, первые автомобили, тракторы. 18 июля 1937 г. газета «Советская Колыма» сообщила о завершении строительства дороги Нагаево – бухта Гертнера и комплекса морского порта. Значительно удлинилась причальная линия, расширилась портовая площадь.
С середины 1930-х гг. к причалам порта в бухте Нагаева стали подходить самые большие суда Тихоокеанского бассейна – закупленные в Голландии пароходы «Джурма», «Кулу» и «Ягода», входившие в состав тогда же сформированного морского флота Дальстроя. Позднее к ним присоединились и другие, среди которых были пароходы «Николай Ежов» и «Индигирка», теплоход «Советская Латвия». На них доставляли не только грузы, но и рабочую силу – заключённых и вольнонаёмных.
В 1940 г. вступил в строй второй причал.
В годы Великой Отечественной войны Нагаевский порт стал важным стратегическим пунктом на берегу Охотского моря. Например, только в 1943 г. он переработал 354 тысячи тонн грузов. В то же время суда морфлота Дальстроя занимались перевозкой грузов по поставкам ленд-лиза из портов США. Нагаевцы перечисляли личные сбережения в Фонд обороны, многие добивались отправки на фронт и уходили воевать добровольцами. Даже в такое непростое время руководство порта думало о развитии предприятия, о механизации основных производственных процессов для увеличения пропускной способности. К 1943 г. в Магадан были доставлены по морю первые восемь кранов общей грузоподъемностью 64 тонны, а ещё через год порт получил автопогрузчики и катучие краны по 15 тонн грузоподъемности каждый. Развивалась и инфраструктура: строились подъездные дороги, складские помещения, была создана своя автобаза, а главное, возведен третий причал. За доблестный труд в годы Великой Отечественной войны многие труженики порта были награждены орденами и медалями СССР.
Сразу после окончания войны порт стал расширяться. В 1952 г. здесь был смонтирован первый портальный кран типа «Вашингтон» грузоподъемностью 41,5 тонны, построены два капитальных склада и автовесовая. На следующий год грузооборот порта уже составлял более 500 тысяч тонн в навигацию.
После упразднения Дальстроя Министерство морского транспорта СССР 23 августа 1957 г. передало магаданский порт в ведение Дальневосточного морского пароходства. Это способствовало более быстрому и продуманному техническому перевооружению предприятия. На смену грузчику, занимающемуся перевалкой тяжестей с помощью мускульной силы, шёл квалифицированный портовый рабочий – специалист, имеющий среднее образование, умеющий работать на авто- и электропогрузчиках, кране, лебедке, способный заменить товарища на любом механизме. Зарождались комплексные бригады, которые затем преобразовывались в укрупнённые, способные собственными силами перемещать любые грузы по различным технологическим схемам. Указом от 3 августа 1960 г. Президиум Верховного Совета СССР наградил орденами и медалями шестерых работников Нагаевского порта.
Назревал вопрос о круглогодичной работе, для чего предполагалось использовать ледокольный флот. 25 мая 1963 г. впервые в истории порта ледокол «Москва» осуществил зимнюю проводку судов, чем положил начало круглогодичной проводке судов. В 1965 г. объем грузоперевозок возрос до 934 тысяч тонн, а комплексная механизация работ составляла 50,8%. Под руководством талантливого руководителя А.Н. Шевченко, который руководил предприятием почти 15 лет (1956–1971 гг.), был разработан генеральный план реконструкции порта. Александр Никитович одним из первых удостоился звания «Почётный гражданин города Магадана», его именем назван теплоход океанского класса «Капитан Шевченко».
В 1977 г. нагаевцы становятся победителями Всесоюзного социалистического соревнования, опыт их работы получает широкое распространение среди родственных предприятий отрасли.
16 мая 1977 г. порт Нагаево был переименован в Магаданский морской торговый порт. Через год, 14 июня 1978 г., создается Магаданский транспортный узел, в основную задачу которого входило обеспечение поставок материально-технических ресурсов для нормальной деятельности промышленных предприятий, строек и торговых организаций области. Основную роль в работе узла играет магаданский порт.
За успехи в ускорении обработки судов и широкое внедрение передовой технологии погрузочно-разгрузочных работ Указом Президиума Верховного Совета СССР от 3 апреля 1981 г. Магаданский морской торговый порт награждён орденом «Знак Почёта».
