Redigerer Kolahalvøya (avsnitt)

===Novgoroderne===
Pomorene ble snart fulgt etter av tributtinnsamlere fra Republikken Novgorod, og Kolahalvøya ble gradvis del av Novgorod.<ref name="ATSBook16" /> En traktat fra 1265 av [[Jaroslav av Tver|Jaroslav Jaroslavitsj]] med Novgorod nevner [[Tre Volost]] (russisk: волость Тре), som senere også blir nevnt i andre dokumenter datert så sent som 1471.<ref name="ATSBook16" /> I tillegg til Tre nevner novgorodiske dokumenter fra 1200- til 1400-tallet nevner også [[Kolo Volost]], som grenset til Tre omtrent langs linjen mellom [[Kildinøya]] og Turij-[[odde]]n til [[Turijhalvøya]].<ref name="ATSBook16" /> Kolo Volost lå vest for den linjen, mens Tre var øst for den.<ref name="ATSBook16" />

Innen 1200-tallet ble en formalisering av grensen mellom Republikken Novgorod og Skandinavia tydelig.<ref name="ATSBook17">''Administrative-Territorial Divisions of Murmansk Oblast'', s.&nbsp;17</ref> 
Novgoroderne, sammen med [[Karelere|karelerne]] som kom fra sør, nådde kysten til det som i dag er [[Petsjenga rajon]], og delen av Varangerfjordens kyst nær [[Jakobselva (Sør-Varanger)|Vorijema]], som idag er en del av [[Norge]].<ref name="ATSBook17" /> Samebefolkningen ble tvunget til å betale [[tributt]].<ref name="ATSBook17" /> Nordmennene derimot forsøkte også å få kontroll på landområdene, noe som førte til væpnet konflikt.<ref name="ATSBook17" /> I 1251 førte en konflikt mellom karelerne, novgoroderne, og den norske konges tjenere til etableringen av en novgorodisk delegasjon i Norge.<ref name="ATSBook17" /> Også i 1251 ble den første traktaten med Norge signert i [[Velikij Novgorod|Novgorod]] angående samelandene, og tributtinnsamlingssystemet, noe som gjorde at samefolket måtte betale tributt til både Norge og Novgorod.<ref name="ATSBook17" /> Ifølge traktatens vilkår kunne novgoroderne samle tributt fra samene så langt som til Lyngentuva, som er et landemerke på Fiskerhalvøya i Varangerfjordens sørlige innløp, mens nordmennene kunne samle inn tributt på hele Kolahalvøya, bortsett fra i den østre delen av [[Terskij-kysten]].<ref name="ATSBook17" /> Ingen statsgrenser ble etablert ved traktaten av 1251.<ref name="ATSBook17" />

Avtalen førte til en kort periode med fred, men væpnet konflikt fortsatte ikke lenge etter.<ref name="ATSBook17" /> Nedskrivninger dokumenter angrep av novgoroderne og karelerne mot Finnmark og Nord-Norge så tidlig som 1271, og fortsatt godt inn på 1300-tallet.Fyrstedømmet Novgorod utførte tilsammen 11 angrep langs Norskekysten helt ned til Troms fylke.<ref name="ATSBook17" /> Den offisielle grensen mellom Novgorod, Sverige og Norge ble etablert ved [[traktaten i Nöteborg]] den 12. august 1323.<ref name="ATSBook17" /> Avtalen fokuserte hovedsakelig på [[det karelske nes]], og grensen nord for [[Ladoga]].<ref name="ATSBook17" />

En annen traktat som tok for seg grensene i nord var [[Traktaten i Novgorod (1326)|traktaten i Novgorod]], signert med Norge i 1326, som endte tiår med grensetrefninger i Finnmark.<ref name="ATSBook18">''Administrative-Territorial Divisions of Murmansk Oblast'', s.&nbsp;18</ref> Per avtalens vilkår avstod Norge alle krav på Kolahalvøya.<ref name="ATSBook18" /> Derimot tok ikke traktaten for seg situasjonen med samefolket som betalte tributt til både Norge og Novgorod, og praksisen fortsatt til 1602.<ref name="ATSBook18" /> Mens traktaten av 1326 ikke definerte avtaler i detalj, bekreftet den grensedemarkasjonen fra 1323, som fortsatte å være mer eller mindre uendret i 600 år, frem til 1920.<ref name="ATSBook18" />

På 1400-tallet begynte novgoroderne å etablere permanente bosetninger på halvøya.<ref name="ATSBook18" /> [[Umba (by i Russland)|Umba]] og [[Varzuga]], de første dokumenterte permanente bosetninger opprettet av novgoroderne, daterer tilbake til 1466.<ref name="ATSBook18" /> Over tid hadde alle kystområder vest for elven [[Pjalitsa]] blitt bosatt, noe som opprettet et territorium der mesteparten av befolkningen var fra Novgorod.<ref name="ATSBook18" /> Administrativt var området delt inn i [[Varzuzhskaya volost|Varzuzhskaya]] og [[Umbskaya volost]], som ble regjert av en ''[[posadnik]]'' fra området ved [[Nordre Dvina]].<ref name="ATSBook18" /> Republikken Novgorod mistet herredømmet over begge disse ''[[volost]]er'' til [[Storfyrstedømmet Moskva]] etter [[slaget ved Sjelon]] i 1471,<ref name="ATSBook18" /> og republikken i seg selv sluttet å eksistere i 1478 da [[Ivan III av Russland|Ivan III]] inntok byen Novgorod. Alle territorier som tilhørte Novgorod, inkludert de på Kolahalvøya, ble en del av Storfyrstedømmet Moskva.<ref name="ATSBook18" />