Началось строительство каменных гостиных дворов, возводившихся по чертежу, присланному из Москвы. Первым руководителем строительства был иностранец Матис Анцин, но он допускал серьезные отступления от проекта. В связи с этим в марте 1671 года был отстранен от руководства работами, а на его место из Москвы прислан талантливый зодчий, подмастерье приказа каменных дел Дмитрий Михайлович Старцев. Тогда же он приступил к строительству (но уже по новому чертежу), закончено оно было к 100-летию Архангельска — в 1684 году. Здание, занимавшее большую площадь, состояло из русского и немецкого гостиных дворов, между которыми располагался каменный город с торговой площадью, служивший одновременно крепостью.
