Согласно Новгородской первой летописи, собор заложен в 1113 году князем Мстиславом Владимировичем.    

Никольский собор является древнейшим из дошедших до нас каменных сооружений на Торговой стороне. Посвящён св. Николаю Мирликийскому, одному из самых чтимых на Руси святых.

Сохранилось предание, что тяжело заболевшему на тридцатом году жизни князю Мстиславу явился во сне святой Николай Мирликийский, повелев отправить посольство в Киев за круглой иконой Николы. Из-за внезапно разыгравшейся бури, посланцы смогли добраться только до острова Липно на озере Ильмень, где и обрели приплывшую по волнам икону с чудотворным образом. Явленную икону доставили в Новгород, и князь получил исцеление. В честь своего чудесного спасения Мстислав приказал заложить на Торговой стороне города, «на Ярославле дворе» храм во имя святителя Николая.

Точная дата окончания строительства неизвестна. Ею принято считать 1136 год, в котором, согласно Новгородской первой летописи, собор был освящён.

Именно в Никольском соборе впервые появился полукруглый, гладкий центральный алтарный выступ. В дальнейшем такого типа выступы стали традиционными для новгородской архитектуры XII века.  Также традиционными для всей последующей новгородской архитектуры стали воспринятые от Софии плоские лопатки стен и круглые без полуколонок барабаны куполов.    

Над входом в храм располагались княжеские полати (хоры).  Собор возводился как дворцовая княжеская церковь. Первоначально в эту часть храма попадали через дверной проем, обнаруженный во втором ярусе западного прясла южной стены, которой соединял княжеские полати с переходом во дворец. Отсутствие внутреннего сообщения между нижним и верхним этажами говорит об их намеренной изолированности.

Первые существенные перестройки храма были предприняты уже в середине  XII века  - в связи с превращением дворцовой княжеской церкви в городской собор, у стен которого собиралось вече. Главным «демократическим» преобразованием этого периода стала каменная винтовая лестница для подъема на полати. При этом  кладка лестницы частично закрыла роспись, законсервировав её на долгое время.

За долгую историю храм прошел сквозь длинную череду пожаров и следовавших за ними перестроек и чинок. В ХVIII веке,  по словам архимандрита Макария, Никольский собор «почти не отличался от самых бедных церквей, по внешнему и внутреннему устройству»: были разобраны верхние части четырёх малых барабанов, винтовая лестница, центральная часть свода хор, центральная часть стены нартекса, расширены некоторые окна, устроена четырёхскатная крыша над основным объёмом и шлемовидная глава над центральным барабаном. Но уже XIX век вошел в историю собора устройством благолепия: новое убранство приделов, чугунный пол и новый иконостас.       

Сведений об упразднении Никольского собора как действующего храма после Октябрьской революции не обнаружено; по данным на июнь 1921 года храм был действующим. В 1933 году собор стал доступен и для обычных посетителей, совместив в себе функции храма и музея.

В годы оккупации Новгорода немецко-фашистскими захватчиками храм был превращен в казарму для солдат. Иконостас был разобран, местный ряд иконостаса - практически утрачен. В 1945 году памятник передан церкви, в 1962 году возвращён музею. С 1963 года здесь размещалась экспозиция научного атеизма и планетарий.

Стараниями реставраторов в конце прошлого века храм восстановлен в своих исконных формах и является жемчужиной новгородской архитектуры.

В настоящее время в Никольском соборе представлена постоянная выставка «Никольский собор: исследования и реставрация», размещаются временные музейные выставки. 

Сочетание подлинной древности, современных технологий  и тематических экскурсов делают этот памятник архитектуры необычайно интересным для любого посетителя.

Расписан Никольский собор был вскоре после окончания строительства. О монументальном характере изображений и чистом, звучном колорите древней росписи дает представление то немногое, что смогло пережить бурные века истории храма. Значительная часть живописи утрачена в XVIII-XIX веках, отдельные фрагменты уцелели в тех местах, что ещё в древности были заложены кирпичом.

В конце XVII века под кладкой лестницы были обнаружены фрагменты одного из самых древних на Руси изображений «Страшного суда»: часть фигуры Сатаны, восседающего на чешуйчатом звере в углу, увитые  змеями ноги грешников и часть изображения огненной реки с увлекаемыми потоком головами грешников. В нижнем  регистре росписи уцелела часть композиции «Иов на гноище». Эта сцена иллюстрирует один из эпизодов ветхозаветной книги Иова, которую знали в домонгольской Руси. Изображен пораженный проказой праведный Иов, сидящий за городской стеной на гноище и беседующей со своей женой, которая с состраданием, но и с невольным отвращением, подает ему на длинном ухвате пищу и питьё. Её лик представляет собой один из самых совершенных художественных образов во всем живописном наследии Новгорода XII века.

В 1997 году к уже известным росписям древней композиции «Страшный суд» добавились фрагменты изображений ада, которые были открыты в ходе устройства каналов для отопления собора в уровне междуэтажного перекрытия.

Кроме этих росписей от XII века до нас дошли древние фресковые орнаменты в откосах некогда заложенных окон барабана центральной главы, нижних окон алтарной части и основного объема собора. В полукружье алтарной апсиды просматриваются фрагменты фигур святителей. Наилучшее по сохранности изображение – монументальная фигура Лазаря, епископат Кипрского, - видна на восточном склоне светового пролета из алтаря в южную апсиду. Приемы энергичной моделировки – с плотными пробелами на лбу, над дугами бровей, вокруг глаз, по гребню носа и по сторонам его крыльев, - находят ближайшие аналогии в киевской художественной традиции, в особенности – в мозаиках Михайловского Златоверхого монастыря.