Сам округ был создан вместе с Магадана 14 июля 1939 года по ходатайству Хабаровского крайкома партии и крайисполкома Указом Президиума Верховного Совета РСФСР в составе Хабаровского края, с центром в населённом пункте Магадан, в составе Ольского, Северо-Эвенского и Среднеканского района. Этим же Указом посёлок Магадан преобразован в город, население которого составляло 30,7 тысячи человек.
13 августа 1939 года в Магадан пришла телеграмма И. В. Сталина, в которой сообщалось, что товарищи, принявшие решение об организации Колымского округа, поступили неправильно, и предлагалось эту ошибку исправить.
Сталин считал, что предложение оргбюро по Колымскому округу об освобождении Дальстроя от важнейших гражданских и политических функций и превращение его в обычный специализированный главк схематично и нежизненно. По мнению Сталина, «Дальстрой — комбинат особого типа, работающий в специфических условиях, и эта специфика требует особых условий работы, особой дисциплины, особого режима».
Оценивая эту ситуацию, начальник Политуправления Дальстроя полковой комиссар С. К. Моренков писал в Секретариат ЦК ВКП(б): «Президиум Верховного Совета РСФСР по предложению Хабаровского крайкома партии и крайисполкома издал Указ об образовании Колымского округа. Указ создал на Колыме, наряду с окрисполкомом, и окружной комитет партии, что при наличии Политуправления, являющегося вышестоящим органом власти на Колыме, вносило определенную дезорганизацию в партийное руководство.
Разрядку этому положению дал тов. Сталин в своей телеграмме от 13 августа 1939 г., заявив, что создание окружкома он считает ошибкой, которую придется исправлять на днях, т. к. достаточно и целесообразно существование на Колыме Политуправления, чрезвычайной формы партийного руководства, имея в виду, что здесь, как говорит тов. Сталин, основная рабочая сила по добыче металла, вся или почти вся, — заключённый элемент, требующий особого режима».
