Своим рождением город обязан бухте, расположенной между западным берегом Кольского залива и островом, лежащим к югу от устья Оленьей губы, в десяти километрах от выхода в Северный океан.
Сведения об этой местности восходят к XVI веку. В 1574 году царский писец Василий Агалин, составляя податную книгу, среди оброчных угодий Печенгского монастыря отметил сенокосные угодья - "в Кольской губе... за Оленьим островом поженки", за которые монахи платили казне "по десять денег на год".
Первое поселение при бухте возникло в конце правления Петра Великого. 8 ноября 1723 года царь подписал указ о создании казенного Кольского китоловства. Промысловой базой для него была избрана гавань, впоследствии получившая название Екатерининской.
Сохранился документ, в котором перечислены все сооружения, сделанные в 1724-1729 годах. В том документе, в частности, говорится: "Гавен для зимовья и починок кораблей и прочих судов, и при том 3 избы для купоренья бочек... 4 анбара для клажи провианта, кузницы, 2 сарая, компанейский двор, в нем 4 ямы сальных, меди в салогрейных котлах 105 пуд 2 фунта; 6 чанов сальных, 2 избы с сень-ми, да кузница, 6 магазинов (складов), погреб, анбар, лошадь, при том дворе пристань для выгрузки; всему двору и прочему цена, например, 3000 рублев".
Китобойная компания имела на Кольском заливе три промысловых корабля и "при них 3 бота и 19 шлюпок" и для разъездов яхту общей стоимостью 23004 рубля 50 копеек.
Предприятие оказалось убыточным, и было ликвидировано. Оставшиеся постройки временами использовались как жилые помещения для промышленников и мореходов.
Кем и когда дано название "Екатерининская гавань", пока не установлено. При Петре Великом бухта именовалась просто "Гавань", но в документах начала 40-х годов XVIII века она уже значится как "Катерингавань" и "Екатерининская гавань". Возможно, название появилось при императрице Екатерине I (17251727 гг.). Вероятно, в архивах Адмиралтейской коллегии, хранящихся в С.-Петербурге, можно найти ответ на этот вопрос.
В связи с нараставшей угрозой шведского нападения на Русский Север в конце 30-х годов XVIII века в Архангельске началось строительство военных кораблей. Было принято решение о крейсерстве русской эскадры в водах Мурмана и северной Норвегии. В 1740 году с архангельских стапелей сошло семь многопушечных кораблей. Выход их в открытый океан надолго задерживался льдами Белого моря. Поэтому в качестве зимней стоянки боевых судов решили использовать Екатерининскую гавань.
В Колу выехали командированные Адмиралтейской коллегией лейтенант Винков и геодезист Зубов с заданием сделать опись гавани, "чтобы узнать удобно ли будет в зимнее время стоять там кораблям и фрегатам, и к защищению их сделать обороны, а для клажи провиантов и материалов построить магазины и для служителей покои". В распоряжении Винкова имелись 2 бота и 2 шлюпки под командованием навигатора Михаила Страхова.
Все лето 1741 года производилось описание Кольского залива и составление карты местности. Тем временем Швеция 28 июля напала на Россию; война длилась до 16 июня 1743 года.
Адмиралтейская коллегия сочла полученные от Винкова карты недостаточными. В 1742 году в помощь Винкову "для съемки плана будущей крепости" был прислан опытный инженер. На этот раз задание было выполнено успешно. Появилась довольно надежная карта Кольской губы со всеми заливами и Екатерининской гаванью.
В Архангельске была сформирована Северная эскадра во главе с вице-адмиралом П. П. Брендалем. В Екатерининской гавани спешно построили две казармы, госпиталь и другие необходимые помещения. Здесь в 1741-1742 годах зимовали суда: "Леферм" (66 пушек), "Исаакий" (54 пушки), "Пантелеймон" (54 пушки) и фрегат "Аполлон" (32 пушки), которыми командовал капитан В. Ф. Льюис. В летнее время суда курсировали в северных водах. Вскоре к ним присоединились корабли "Счастье" и "Фридемакер" (по 66 пушек). Осенью 1743 года все суда ушли в Кронштадт.
Вплоть до 1915 года гавань ни разу не использовалась для военных целей, но неоднократно служила для других надобностей.
Во время бурной погоды в бухте нередко укрывались торговые и промысловые суда, в том числе вывозившие лес, сплавляемый по Туломе. В одном из документов отмечается: "В 1745 году посланы были в Екатерининскую гавань для исправления и килевания находившегося тогда с лесами корабля корабельные два подмастерья". Компания графа П. И. Шувалова неподалеку от Екатерининской гавани устроила таможенный досмотр (брандвахту) иностранных кораблей. В поморской народной лоции середины XVIII века говорится: "Пройдучи Медведок остров, где брандвахта содержится... на наволоке есть крест, прям губы стоят корабли и лодки".
Местное население, по свидетельству гидролога М. Ф. Рейнеке, называло Екатерининскую бухту "Корабельным урочищем" или сокращенно - "Корабельной", а остров Екатерининский - "Гаванским".
В марте 1765 года в Екатерининскую гавань пришли корабли "Чичагов", "Панов" и "Бабаев" под командованием В. Я. Чичагова с экипажем 178 человек. Воеводская канцелярия извещала архангельского губернатора: "Прибыли в Кольский острог из Екатерининской гавани адмиралтейские служители и требуют от Кольской ратуши немалого числа лодок и оленьих подвод". 9 мая 1765 года арктическая экспедиция Чичагова отправилась в высокие широты, в ноябре она возвратилась из плавания и зимовала в Кольском заливе, квартируя преимущественно в Коле. После второго плавания по Ледовитому океану суда ушли в Архангельск.
Летом 1767 года в Коле, на горе Соловараке, началось строительство временной астрономической обсерватории для наблюдения за редким явлением - прохождением Венеры по диску Солнца, которое ожидалось 23 мая (3 июня по новому стилю) 1769 года. В Екатерининскую гавань на трех судах доставили из Архангельска 665 бревен, 1140 тесин, 12000 кирпичей и другие материалы и инструменты. Оборудованием обсерватории и наблюдениями руководил профессор С. Я. Румовский.
В 1771 году изучением Мурмана занимался сотрудник Петербургской Академии наук Н. Я. Озерецковский. В своем описании Кольского края он отметил удобство Екатерининской гавани, возле которой были "построены светлицы для пребывания мореходцев... В ней никакая буря судов обеспокоить не может; она же ни в самые жестокие морозы не замерзает. Можно сказать, что заливец сей, как бы нарочно, сделан для пристани".