W sierpniu 2001 r. restrukturyzująca się marynarka wojenna Norwegii (Sjøforsvaret), podzielona na Flotę (Kysteskadren), Straż Przybrzeżną (Kystvakten) oraz ośrodki szkoleniowe, utworzyła w tej pierwszej, obok flotylli fregat, okrętów podwodnych i minowców, flotyllę przybrzeżną (Kyststridsflotilje), co oznaczało też kres istnienia z końcem roku odrębnego pionu artylerii nadbrzeżnej. W ramach nowej flotylli, oprócz dowództwa kutrów torpedowych (MTB-kommandoen) oraz jednostki specjalnej płetwonurków bojowych, zwanych morskimi jegrami (Marinejegerkommandoen, MJK – „SPECIAL OPS” 4/2013), przewidziano miejsce dla planowanej KJK. Formalnie powołano ją 10 grudnia 2001 r. w bazie Trondenes, 3 km powyżej dwudziestotysięcznego Harstad, na północnowschodnim cyplu Hinnoya – największej wyspy w archipelagu Vesterålen i kontynentalnej Norwegii, przy jej północnym wybrzeżu, na wysokości Narwiku. Pierwszym dowódcą przybrzeżnych jegrów został mianowany kmdr por. Einar Haarberg, którego zastąpił następnego roku Kommandørkaptein Morten Einbu.
KJK składała się początkowo z małego sztabu, kompanii rozpoznawczej Alfa, kompanii Bravo o charakterze zwykłej piechoty morskiej, lekkiej baterii rakiet Hellfire, kompanii logistycznej oraz eskadry łodzi (fartøyskvadron). Łącznie było to 430 żołnierzy marynarki wojennej, których liczba miała w ciągu następnych trzech lat wzrosnąć do 500, a dalsze plany przewidywały podwojenie tej liczby. Już w 2002 r. Kystjegere wzięli udział w dużym ćwiczeniu NATO pk. „Strong Resolve”, prowadząc na rzecz norweskiego zgrupowania zadaniowego (NOTG) aktywne rozpoznanie oraz atakując zlokalizowane cele pociskami RBS 17, po skrytym przeniknięciu w rejon działania sekcji z LMB i pododdziałów osłonowych. Kolejny rok upłynął na wytężonym treningu, doskonalącym umiejętności bojowe personelu z zaciągu ochotniczego oraz ocenianiu rozwiązań organizacyjnych, taktycznych i analizie nabytych doświadczeń. W 2004 r. jednostka wdrażała nowe uzbrojenie (niemieckie kbk HK G36KV2 i granatniki AG36), a cała kompania Alfa uczestniczyła w ćwiczeniu pk. Joint Winter, włączona w kontyngent Royal Marines Commando. Uzyskane wówczas wysokie oceny przełożyły się na dalsze zacieśnianie kontaktów szkoleniowych z brytyjskimi odpowiednikami, w tym m.in. zaproszenie na ich trzymiesięczny kurs dowódczy dwóch oficerów KJK, którzy powrócili do Norwegii z prawem do noszenia zielonego beretu królewskich komandosów.
Na początku 2005 r. zapadła decyzja, by – ze względu na malejące prawdopodobieństwo dużych, konwencjonalnych wojen, a rosnące konfliktów asymetrycznych i małej intensywności – zamiast rozwijać ilościowo KJK, zmniejszyć jej stan liczebny oraz pogłębić przeznaczenie rozpoznawcze jako morskiej jednostki ISTAR (ang. Intelligence, Surveillance, Target Aquisition, Reconnaisance – wywiad, obserwacja, namierzanie celów i rozpoznanie). Rozwiązaniu uległa kompania Bravo, natomiast Alfa intensywnie trenowała skryte przenikanie na wybrzeże kontrolowane przez przeciwnika, prowadzenie obserwacji oraz patroli rozpoznawczych w jego ugrupowaniu i na polu walki. Nie zrezygnowano jednak z utrzymania zdolności LMB, doskonalącej jako Charlie-skvadron taktykę współdziałania obsług wyrzutni RBS 17 z kutrami S90N, którą zainteresowały się także piechoty morskie Wielkiej Brytanii i Holandii. Kystjegere zdobywali kolejne doświadczenia na trzytygodniowych ćwiczeniach pod okiem ekspertów z Royal Marines w Szkocji, nawiązali kontakty szkoleniowe z US Navy oraz mieli okazję porównać swe umiejętności z 2. batalionem holenderskiego Korps Mariniers podczas treningu górskiego w północnej Norwegii. Ważnym sprawdzianem był dla KJK również udział w dużych międzynarodowych ćwiczeniach pk. „Battle Griffin 2005”, w ich kraju, z udziałem przedstawicieli 15 armii NATO. Przybrzeżni jegrzy zacieśnili także współpracę z nurkami-minerami marynarki (Minedykkerkommandoen, MDK), ucząc się współdziałania w różnych warunkach. Po czterech latach rozwoju, wypracowywania docelowych zdolności taktycznych i odpowiedniej formy organizacyjnej, KJK, której kolejnym dowódcą został Kommandørkaptein Per Anders Bakke, osiągnęła 17 sierpnia 2005 r. gotowość operacyjną, a już we wrześniu grupę jegrów na stridsbatach włączono do NOTG udającej się na ćwiczenie pk. „Green Osprey” na wybrzeżu Senegalu.