Небольшая церковь Андрея Стратилата возникла не ранее конца ХVII или начала ХVIII века на разобранных развалинах древней Борисоглебской церкви, которую в 1167 году выстроил боярин Сотко Сытинич. В 1969 году внутри церкви Андрея Стратилата была раскопана хорошо сохранившаяся лестничная башня Борисоглебской церкви. Лестница в башне вела на полати (хоры) церкви.
Изначально на месте церкви в 1167 — 1173 годах был построен каменный храм Бориса и Глеба — величественная, трехапсидная, шестистолпная постройка с лестничной башней. В 1405 году из-за пожара охватившего Людин конец церковь сильно пострадала и в 1441 году по указу архиепископа Евфимия II строится новый храм на старом основании. При строительстве была разобрана лестничная башня и на её основании сооружён отдельный придел Андрея Стратилата.
Перестроенный в XV веке Борисоглебский собор изображён на иконе «Видение пономаря Тарасия» конца XVI века, украшенный громадной фреской-иконой и увенчанный двумя главами. Одна из них (маленькая) символически указывает на существование придела Андрея Стратилата. Достаточно чётко можно увидеть придел Андрея Стратилата на шведском плане 1611 года, где он показан с юга у одноглавого основного объёма.
При завоевании Новгорода шведами в начале XVII века собор подвергся сильному разрушению.
В 1682 году Борисоглебский собор обрушился и был разобран до основания, а сохранённый придел Андрея Стратилата расширен к востоку и обращён в самостоятельную церковь. Таким образом, ныне существующее здание является результатом двух основных строительных периодов. От XV века сохраняются стены западного объёма и северная стена восточной пристройки. Они сложены из волховского плитняка, ракушечника и кирпича. Архитектурное оформление западного портала с арочным завершением, декоративной бровкой снаружи и треугольной перемычкой внутри характерно для новгородского зодчества XV века. Восточная и часть южной стены, так же как и своды, сложены из кирпича в XVII веке.
В первой половине XIX века храм перестраивается. Тогда был устроен новый свод в западном объёме и новый карниз, заменена кровля, сделана небольшая главка и звонница, а также укреплены фундаменты под северной стеной.
В годы Великой Отечественной войны церковь пострадала: была повреждена кровля, осыпалась штукатурка, разобраны полы.
В 1947 году здание отремонтировали. В 1969 году под руководством профессора М. К. Каргера произведены исследования оснований лестничной башни XII века внутри и снаружи западного объёма церкви. Были открыты нижние участки стен и хорошо сохранившаяся кладка центрального круглого столба с несколькими ступеньками винтовой лестницы.
В 1970-е годы состояние памятника начало резко ухудшаться — стены пошли трещинами. Под руководством архитектора Новгородской реставрационной мастерской Г. М. Штендера были осуществлены противоаварийные работы.
В 2000 -2003 годах проведены реставрационные работы фирмой «Десна» по проектам О. Н. Коваленко и Л. Г. Марковой. В процессе работ были укреплены несущие конструкции здания: кладки стен, сводов, фундаментов. Из известняковых плит выложили пол в западном объёме таким образом, чтобы выявить форму круглого основания и стен лестничной башни. Тогда же под руководством Е. И. Серегиной, художниками — реставраторами Межобластного научно-реставрационного художественного управления г. Москвы была раскрыта и укреплена настенная живопись XVI — XVII веков внутри храма.
На северной стене западного объёма церкви в нижнем регистре изображена процессия святых, обращённая к алтарю. Первым с востока представлен Андрей Стратилат.
На западной щеке триумфальной арки в центре — композиция «Знамение Божьей Матери» в медальоне — образ, особенно почитаемый в Новгороде. По сторонам от неё — изображения библейских царей Давида и Соломона и неизвестных святых в медальонах.
На стенах западного объёма, в верхнем регистре фрагментарно сохранилась грандиозная композиция «Вознесение Христа». На южной и северной стенах — 12 апостолов в рост, в трёхчетвертном повороте, обращённые к Богоматери. Образ её написан на западной стене. За спиной Богоматери — два ангела в белых одеждах. Уцелели только нижние части фигур Богоматери и ангелов. Из 12 апостолов только у одного сохранилось личное письмо. Остальные лики были утрачены при устройстве позднего свода. Погибло и изображение Христа в сиянии с ангелами и серафимами, которое находилось на утраченном своде.