Существуют летописные сведения о том, что уже в 1230 году на месте современной церкви стояла деревянная. Она именовалась как «церковь у скудельни» или в «пропастех».
Место получило известность благодаря страшному голоду 1230 года. Голод в Новгороде случился настолько сильным, что жители умирали целыми семьями и заниматься их погребением было некому. Тогда же, по распоряжению новгородского архиепископа Спиридона, рядом с церковью была устроена скудельница. К ней был приставлен специальный человек по имени Станила. Ему полагалось «возити мертвецы на кони и тако беспрестани во вся дни влачаше и наполни до верха».
Деревянный храм не раз горел и перестраивался. В 1358 году четвёртая Новгородская летопись упоминает о каменной церкви, построенной на этом месте мастерами Андреем Захарьиным и Даниилом Козиным. Храм был больше современного почти в два раза. Летописные сведения о нём несколько противоречивы; так, например, Комиссионный список Новгородской первой летописи упоминает под 1358 годом о строительстве деревянной церкви[1]. Согласно имеющимся данным, можно предположить, что храм разрушился до 1405 года.
В 1432 году по указанию новгородского архиепископа Евфимия возводится деревянная церковь. Затем, в 1454 году закладывается и в течение года строится каменный храм, дошедший до наших дней.[2]
В XVI веке в храме было сооружено перекрытие, разделившее его на два этажа: нижняя часть — подцерковье, верхняя — сама церковь. Тогда же была разобрана колокольня и западный притвор, кровля была перестроена в четырёхскатную. В 1904 году, после пожара, кровлю сделали восьмискатной.
Архимандрит Макарий в XIX веке в своих записках отмечал, что место, где стоит церковь, называлось в его время Владычным или Митрополичьим островом. В то время она находилась в саду и вместе с садом и подворьем принадлежало Новгородскому Архиерейскому дому. В Архиерейском доме останавливались приезжавшие из Москвы церковные иерархи.
Церковь Двенадцати Апостолов слабо пострадала в годы Великой Отечественной войны. Восстановлена и отреставрирована в 1949 году. В 1957—1958 годах, при дальнейшей реставрации, было также произведено укрепление и исследование памятника. Внутреннее убранство, древнерусские фрески, так и не были восстановлены; главный западный вход с папертью замурован.[3]