Офіційною датою виникнення Новгорода прийнято умовно вважати 859 рік, виходячи зі згадки міста в Никонівському літописі (компіляція XVI століття). При цьому в самому літописі не сказано про заснування міста саме цього року, але під літом 6367 (859 рік) міститься запис про смерть новгородського старійшини Гостомисла. Автором офіційної дати заснування міста став історик М. Е. Тихомиров, який виступив з доповіддю на науковій конференції в Новгороді напередодні 1959 року, що дало підстави відзначити того року 1100-річчя Новгорода.

В арабських джерелах X століття згадується пункт Ас-Славія (Слава, Салау) як один з трьох центрів русі (русинів) разом з Куябою (Києвом) і Артанією (Артою, ідентифікація неясна, Леонтій Войтович припускає, що теперішній присілок Смоленська Гньоздово найбільше відповідає локалізації Арти[8]). Вважають, що мова йде про попередника Новгорода — «старе місто» ільменських словен.

За припущеннями деяких істориків, найраніша іноземна згадка Новгорода як про Nεμογαρδάς[9] (у перекладі Німогард, Немогард або Неб(в)огард[9]) міститься у творі 949 року візантійського імператора Костянтина Багрянородного «Про управління імперією».

Раніше частина дослідників вважала, що у скандинавських сагах місто називається Гольмґардом (або Холм-Городом, Holmgard, ісл. Holmgarður) столицею Гардариків. Частина істориків ототожнила з «першим Новгородом» Рюрикове Городище або Ладогу[10]. Молодий Б. Греков, досліджуючи волость Жабка, висловив припущення, що Новгород міг мати кілька «кінців» і погост, які склали одну велику волость. Зі зменшенням шансів віднайти укріплене Новгородське поселення, раніше ХІ століття, почали складати версію про Холм-Город на Славенському кінці, який скандинави як предтечу Новгорода називали Гольмґардом[11].

В німецьких джерелах називається Острогардом.

У Новгороді відбуваються також основні дії епічного літературного твору XVII століття «Сказание о Словене и Русе и городе Словенске» і билини про Садка.

Руські літописи подають різні версії виникнення міста. За «Повістю времених літ» (Лаврентієвський список), місто існувало ще до моменту приходу Рюрика в 862 році і було засноване ільменськими словенами в процесі їхнього розселення після міграції з Дунаю. Згідно з Іпатіївським літописом: «Словене же седоша около езера Илмера и прозвашася своимъ именемъ и сделаша городъ и нарекоша и Новъгородъ». Рюрик, за Іпатієвським списком, спочатку княжив у Ладозі і лише після смерті братів «пришед къ Ильмєрю и сруби городе надъ Волховом и прозваша и Новъгород» (спостерігається деяка невідповідність з повідомленням того ж літопису про заснування міста словенами). На думку Бориса Рибакова, певні епізоди «Повісті временних літ» з ініціативи князя Мстислава-Гаральда Володимировича, який тривалий час правив у Новгороді на Волхові, відредагували (сфальсифікували) легендою про Рюрика для висунення на провідну роль Новгорода в становленні Руської держави[12].
Новгородський I літопис молодшого ізводу згадує новгородців у недатовані часи легендарного Кия.

За тим же Новгородським першим літописом молодшого ізводу «город» був закладеним Володимиром Ярославичем 1044 року[15].

Дослідження, проведені російськими науковцями під проводом керівника Новгородської експедиції академіка РАН В. Л. Яніна та відомого лінгвіста А. А. Залізняка, припускають, що мова берестяних грамот ближча до стародавньої польської (лехітської) мови та відрізняється від південно-руської мови Київської Русі. Можливо, що джерелом заселення Новгородських земель стала слов'янська південна Балтика.[16]

Всі події, зафіксовані в літописах про Новгород до 1044 року, мають стосунок до іншого міста[10]. Скандинавські джерела, зокрема, саґи, до XIII ст. не знають Новгорода. Князів Володимира Святославича та Ярослава Мудрого вони називають «конунгами Гольмґарда».[17]

Археологічні дослідження розкрили невідповідність між картиною, створеною істориками на підставі письмових джерел, і станом археологічних матеріалів по самому ранньому періоду в історії Новгорода[18][19].

Новгород, що виник серед боліт на вологому ґрунті, характеризує феноменальний ступінь збереження своїх старожитностей, а завдяки особливостям забудови має надзвичайно чітку стратиграфію культурного шару[19][20]. Археологічні дослідження з кінця XIX ст. (систематичні з 1932 року), що проведені на більш ніж 50 ділянках та площі понад 30000 м², розташованих як у центрі, так і на периферії Новгорода (в межах його валів), виявили тільки на двох із них (Неревському і Троїцькому розкопах) шари, що датуються серединою X ст.[21]. Це засвідчило існування в межах майбутнього Новгорода у Х ст. декількох окремих невеликих поселень, розділених пустопорожніми просторами. На іншій території, частина якої розташована навіть у центральних районах, життя почалося в XI, XII, а часом і в XIV століття.[22][23]. Припускають, що найдавніші поселення, на основі яких формувався город, називалися Славно або Холм-город, Людин і Наревський[24][25]. Об'єднання цієї рихлої доміської структури в «город» відбулося поступово на рубежі Х—XI ст. навколо загальноміського храму і єпископського двору в міру княжої централізації та християнізації з Києва, що вказує на те, що Русь не починалася з так званого «Великого Новгорода». Будівництво Дитинця (кремля) і кам'яного Софійського собору в середині XI ст. завершило цей процес[26].

Найдавнішу з новгородських будівель, досліджену археологами, датують 953 роком[19]. Найдавніші з досліджених дерев'яних мостових на території сучасного Новгорода, які прокладали для зручності пересування по заболоченій території, також датують X століттям (за методикою дендрохронології)[27]: найранішнє мощення в Наревському поселені датоване 953 роком, у поселені Славно (Холм-городі) — 974 роком. У 989 році зведена перша дерев'яна церква Софії[25]. Датування будівництва дубового Новгородського дитинцю за комплексом археологічних матеріалів може бути визначено першими десятиліттями ХІІ ст.[28]

Для дослідження історії середньовічного Новгорода корисні дані про Рюрикове городище[29] (в межах міста з 1999 року) за 2 км на південь від історичної частини Новгорода, де вдалося достовірно встановити наявність поселення з другої половини IX століття[30]. Взамін концепції про Ладогу, як попередницю Новгорода, на початку ХХІ ст. російськими вченими висунута гіпотеза про взаємозв'язок Городища і Новгорода як «міста старого» і «міста нового»[31][32].

У той же час археологічні дослідження засвідчили, що Городище різко відрізнялося від раннього Новгорода соціально-економічним ладом і етнічним складом населення. На відміну від Новгорода, де в культурі городян не вловлюється вплив скандинавів, Городище було одним із скандинавських центрів дальньої торгівлі[33], пов'язаним з транзитними військово-торговельними комунікаціями Східної Європи — Волзьким торговим шляхом[34][35]. При цьому, якщо в структурі археологічних комплексів інших центрів «східної торгівлі» присутні практично всі види археологічних пам'яток — в схожому Тимерівському комплексі (під Ярославлем): селище, п'ятсот документованих курганних могильників з різними варіантами ритуалу, клади арабських монет ІХ ст., — то Городище біля Новгорода включає лише поселення з оборонно-гідротехнічним укріпленням (після зведення, у кінці ІХ ст. було розмите паводками і більше не поновлювалося[36]), а також клади монет. Поховальні древності в структурі комплексу Рюрикового Городища відсутні[34]. Приналежність Городища до скандинавського світу епохи вікінгів свідчать ритуали, пов'язані з масовими жертвоприношеннями коней, черепи яких «прикрашали» оборонні споруди[37].