Каменная крепость Вологды не сохранилась, и это первое, что нужно о ней знать: на поверхности от неё почти ничего не осталось. Она занимала 56 гектаров, по периметру тянулось 3108 метров стен, на них стояли 22 башни и 7 ворот. Сегодня кремлём называют Архиерейский двор внутри той крепости: около 2,3 гектара, каменная ограда и 3 башни; из 4 ворот 3 заложены.
Строительство началось 28 апреля 1566 года, в день апостолов Иасона и Сосипатра, — отсюда второе имя крепости, Насон-город. Иван Грозный готовил здесь резиденцию. Работами руководил, по одним сведениям, англичанин Хемфри Локк, по другим — русский инженер Размысл Петров. К 1571 году успели выложить каменную стену с 9 башнями по юго-востоку и 2 башни на юго-западном углу; после неожиданного отъезда царя стройка остановилась.
Недостроенные прясла прикрыли деревянным острогом с шатровыми башнями. В 1612 году часть стен сгорела при нападении польско-литовского отряда, в 1632-м острог обновили. Внутри, у Пятницких и Спасских ворот, шумела торговая площадь: в 1627 году на ней было 11 рядов, в 1711-м — уже 22. К середине семнадцатого века крепость потеряла военное значение, кирпич пошёл на церкви и гражданские дома, паводок 1670 года размыл вал, и восстанавливать его не стали. В 1822—1823 годах при устройстве бульваров разобрали последнюю башню — Пороховую.
Стены исчезли, но рельеф их помнит. Рвы читаются как пруды парка ВРЗ и русло Золотухи, вал — как насыпь в том же парке, фундаменты — под торговыми рядами на улице Мира. Раскопки 2011 и 2013 годов открыли основания башен, считавшихся утраченными. В 2022 году раскопали 2 стены ещё одной. Найденные фрагменты должны попасть в федеральный реестр памятников.
Живым ядром крепости остался Архиерейский двор. Его каменные стены возвели в 1671—1675 годах при архиепископе Симоне, сразу после того как рядом поднялись каменные палаты. По одной версии, стройка в голодные годы давала людям заработок; по другой, стены с самого начала были не столько обороной, сколько знаком — крепостью духа внутри государевой крепости. Название «кремль» за двором закрепилось в 1855 году, когда Андрей Муравьёв назвал его малым кремлём.
Так в Вологде появились 2 кремля: один в земле и в старых планах, другой — в кирпиче и в музейных залах. Крепость Ивана Грозного исчезла как сооружение, но осталась в городской памяти; Архиерейский двор сохранил стены и принял имя исчезнувшей крепости, под которым его знают теперь.
