Крепость была заложена в 1701 году по личному указанию царя Петра I для защиты Архангельского фарватера в связи с ожидаемым нападением шведов во время Северной войны 1700—1721 годов. Автор проекта — немецкий инженер Георг-Эрнест Резе. Считалась одной из лучших крепостей в России.
Крепостные сооружения включали в себя квадратную в плане четырёхбастионную цитадель и ряд так называемых внешних укреплений: фоссебрею, ров, равелин, прикрытый путь, частокол и гласис. Внутри цитадели были отстроены 2 кирпичных (надвратных) здания для размещения коменданта и старших офицеров, 4 пороховых погреба, казармы, склады военной амуниции, башня с флагштоком для поднятия крепостного флага. На центральном плацу располагалась деревянная церковь во имя св. Петра и Павла.
Основные строительные работы на крепости были завершены в 1705 году; полное формирование фортификационного комплекса относится к 1714 году, когда на северной стороне крепости окончили возведение равелина.
В годы Крымской войны (1853—1856), хотя крепость и не принимала участие в боевых действиях, её нахождение на пути к Архангельску сорвало планы нападения на город объединенной англо-французской эскадры. Неприятель не решился войти в устье Северной Двины, опасаясь огня крепостных орудий. Упразднена в 1863 году, а со следующего перешла в ведении Архангельской епархии.
В советское время на территории крепости сначала находилась детская колония-коммуна, позже — исправительно-трудовое учреждение, просуществовавшее до 2006 года. В декабре 2007 года Новодвинская крепость была передана Архангельскому областному краеведческому музею, получила статус памятника федерального значения. С 2008 года на территории крепости ведутся противоаварийные работы. В настоящее время в относительно хорошем состоянии находятся южная и западная части цитадели с комплексами двух главных ворот; остальные фортификационные сооружения сохранились фрагментарно.
