Utena - vienas iš seniausių Lietuvos miestų. Utenos vardas istorijos šaltiniuose sutinkamas tik nuo 1261 metų - tai Lietuvos karaliaus Mindaugo aktas, kuriame Tauragnai, Utena ir Užpaliai laikomi esantys Sėlos ribose. Mindaugas sėlių teritoriją tuo metu dovanojo Livonijos ordinui; kaip nurodo Teodoras Narbutas, dokumento originalas XIX amžiuje buvo Karaliaučiaus slaptajame archyve (nors dažnai abejojama dėl akto autentiškumo, tačiau neabejotina, kad akte minėtos vietovės tuo metu jau egzistavo). Šios vietovės priklauso rytų aukštaičių uteniškių tarmės arealui, kuris laikytinas asimiliuotu sėlių rajonu. Kaip pažymi E. Gudavičius, ten ir ieškotina ir Nalšios vakarinės etninės ribos (Nalšia siejama su vietovėmis vardu Noliškis, kurių netoli Utenos yra net kelios), skyrusios Deltuvos ir Nalšios žemes.

Su senąja Utenos istorija pirmiausia siejami Narkūnų piliakalniai; spėjama, kad XIII amžiuje ten stovėjo Nalšios kunigaikščio Daumanto pilis, prie kurios kūrėsi didesnė gyvenvietė, davusi užuomazgą miestui. Narkūnų piliakalnių, siejamų su Utenos miesto pradžia, radiniai liudija, kad ten jau buvo gyvenama, ginamasi nuo priešų, verčiamasi prekyba ir amatais nuo II tūkstantmečio prieš Kristų pabaigos. Vis dėlto į stambesnę gyvenvietę - prekybos, amatų ir administracinį centrą - išsivystė II tūkstantmečio po Kristaus pradžioje. Kaip pažymi Regina ir Pranas Kulikauskai, tyrinėję Narkūnų piliakalnius, 1975 - 1976 metais, „turbūt nesuklysime, Utenos miesto užuomazgos ieškodami Narkūnų archeologinių paminklų komplekse“. Dar pirmajame tūkstantmetyje prieš Kristų čia būta medinių pastatų, gynybinių įrengimų, kurie ne kartą degė ir vėl buvo atstatomi, paskui kurį laiką piliakalniai buvo apleisti, tik antrojo tūkstantmečio po Kristaus pradžioje didysis piliakalnis iš naujo pertvarkytas, padidintas ir įtvirtintas gynybiniais pylimais, apsauginiais grioviais, gynybinėmis sienomis. Pilies sienos buvo medinės, tinkuotos moliu. Apie puskilometris į rytus nuo piliakalnių mediniuose karstuose buvo laidojami nesudeginti mirusieji. Tad, kaip pažymi P. Kulikauskas, Utenos užuomazgų reikia ieškoti ne Pakalniuose (ten, ežero krante, didžiausias Utenos rajono piliakalnis), bet arčiau Utenos esančiuose Narkūnuose.

	Paminklinis akmuo miesto įkūrimui

Utenos krašto padavimas nukaltas iš Utenos vietovardžio. Vietovardinę Utenio vardo kilmę pažymi ir M. Jučas, kalbėdamas apie legendinius Palemono palikuonis. XVII amžiaus Lietuvos istorijos autorius Albertas Vijūkas - Kojelavčius Utenį vadina Lietuvos bei Žemaitijos kunigaikščiu (apie 1227 metus); jis įkūrė „gyvenvietę Uteną, pavadintą jo vardu, o greta pastatė pilį; miestas ir dabar tuo vardu vadinamas, tačiau netoliese pastatytos pilies teišliko pėdsakai“, - neaišku, kokius pilies pėdsakus jis matė XVII amžiuje. Galime tik spėti, kad naujoje vietoje miestas suplanuotas vykdant valakų reformą XVI amžiuje. Galimas daiktas, kad pirmoji Utenos bažnyčia ir miestas, kaip kalbama padavimuose, buvo prie piliakalnių. Kalbininkas Aleksandras Vanagas neabejoja, kad miesto vardas yra vandenvardinės kilmės, tikriausiai atsiradęs iš upės vardo Utenaitė arba Utenėlė, galbūt senesnis upės vardo variantas buvęs Utena, juk ir dabar Utenoje ir netoli jos yra ežerų ir upelių tuo vardu (Utenas, Utenykštis, Utenėlė).

„Livonijos kronikoje” Hermanas Vertbergės nurodo, kad 1373 metais Livonijos magistras  Vilhelmas iš Vrimusheimo teriojo lietuvių žemę aštuonias dienas, paėmęs beveik tūkstantį belaisvių, neskaitant užmuštųjų; tarp kitų nuniokotų vietovių - Tauragnų, Linkmenų, Giedraičių, Videniškių ir kitų - minimas ir Utenos (Vittena) laukas. Tais pačiais metais kovo 19 dieną Livonijos krašto maršalas Andrejus sudegino Užpalių pilies priešpilį. 1375 metais vasario 5 dieną Livonijos magistras su didele kariuomene nusiaubė Tauragnus, Uteną, Noliškį, Balninkus, Giedraičius ir kitas apylinkių vietoves. Taigi ir XIV amžiaus antrojoje pusėje Utenoje ir apylinkėse ramaus gyvenimo nebuvo. 1433 metų sausio 30 dieną Švitrigailos rėmėjas - Livonijos ordinas viešai paskelbė karą Žygimantui Kęstutaičiui ir, įsiveržęs į lietuvių žemes, plėšė ir degino Linkmenų, Tauragnų, Utenos, Užpalių apylinkes.

Lietuvos didžiojo kunigaikščio Kazimiero valdymo metu (1440 - 1492 metais) iš Utenos smuklių ir pajamų įvairiems asmenims už tarnybą buvo mokamos nemažos pinigų sumos. Taigi Utenos miestas  buvo nemažas (Pagal S. Alexandrovičių, Utena kaip miestelis minimas 1486 metais). Nuo XV amžiaus antros pusės iki XVII amžiaus Utena buvo dvaras priklausantis valdovui, kurį valdydavo jo paskirti vietininkai arba laikytojai: 1489 metais Liutauras Chreptavičius, 1493 - 1499 metais - Vaitiekus Jonaitis Kločka, 1499 - 1507 metais - Mykolas Glinskis, 1508 metais - Ivanas Andrejevičius, 1509 - 1511 metais - Jurgis Radvilas, 1511 - 1516 metais - Petras Aleknavičius, 1516 - 1518 metais - Grigas Astikas, 1519 - 1527 metais - Albertas Goštautas.