The Novodvinsk fortress was founded in 1701 by an order of Peter the Great to protect Arkhangelsk from possible attacks from the seaside. All construction works were finished in 1721. The chief architect was George Rese. Garrison of the fortress could count up to 1000 soldiers. Novodvinsk fortress was the first Russian fortification built in star fort style. Its construction helped to fully control the main fairway to Arkhangelsk that was used by trade and military ships, coming from Europe. The fortress was a corner stone of a fortification complex located in the mouth of the Northern Dvina.

On 25th June in 1701 the vanguard of Swedish military fleet, which had an intention to destroy Arkhangelsk, was defeated there. It was the first considerable Russian victory of the Great Northern war that had saved the main Russian seaport and become a solid foundation for further victories. For several times in the 18th and 19th centuries the fortress was in the state of defense emergency and it played an important role in protection of the Russian North. Some parts of fortification were improved and reconstructed in 1800-1801 by Russian engineer Peter Sukhtelen.

The fortress was visited by two Russian emperors: Peter the Great (1702) and Alexander 1(1819). The fortress was finally abolished in 1863. In the beginning of the 20th century, during the First World War and Russian Civil War there was an artillery supply depot in former fortress. During the Second World War a factory "Konveyer" was organized within the territory of the fortress that produced shells and other ammunition. In 2007 the fortress was given to the Arkhangelsk regional museum for local lore.