Весной 1702 года Меншиков отправляется вместе с Петром в Архангельск, имея должность гофмейстера царевича Алексея, а осенью участвует в осаде Нотебурга. Под Нотебургом впервые проявились его военные дарования.
Известно, что осада и штурм крепости сопровождались огромными потерями русских войск. Отчаявшись в успешном завершении штурма, Петр даже дал команду о его прекращении, но, как это часто бывает на войне, выполнить его повеление помешала случайность – в суматохе сражения посыльный никак не мог добраться до руководившего штурмом князя Михаила Михайловича Голицына, чтобы передать ему царское повеление. В этот критический момент приспела помощь, ее привел поручик Меншиков. Подоспевшие свежие силы определили успех – гарнизон крепости капитулировал.
Петр щедро наградил участников штурма, как офицеров, так и рядовых. Голицын был пожалован полковником Семеновского полка и деревнями. Достойно была оценена и отвага Меншикова. Указом от 18 октября 1702 года царь повелевал: «Преображенского полку поручика Александра Даниловича Меншикова во всяких письмах писать губернатором».[23] Заметим, что должность губернатора Меншиков получил за восемь лет до губернской реформы, после которой в России были учреждены губернии.
Петр едет сначала в Москву, а затем в Воронеж, а оставленный в Шлиссельбурге губернатор развивает кипучую деятельность. Две главные задачи стояли перед начинающим администратором и военачальником: хозяйственное освоение края, использование его ресурсов для нужд войны и защита только что возвращенных земель.
Меншиков преуспел и на том и на другом поприще. Царь поручил Меншикову разыскать место для основания верфи. В феврале тот доносит Петру, что им найдено такое место на реке Свири, где имеются леса, пригодные для постройки не только мелких, но и пятидесятипушечных кораблей. Так, стараниями Меншикова была основана Олонецкая верфь, с которой уже в августе 1703 года был спущен первенец Балтийского флота фрегат «Штандарт».
Верфь находилась под особым присмотром Меншикова. Олонецкий комендант Иван Яковлевич Яковлев едва ли не в каждом письме Меншикова мог прочесть слова: «корабль и другие суды строить с великим смотрением неотложно»; чтобы «пушки лили безо всякого мотчания»; «как наискоряе в деле поспешай»; «чини по сему, не отлагая в даль времени». С верфи поступали обнадеживающие сведения: «На Олонецкой верфи корабельные строения строятся, милостию Божиею, в добром поведении»; «Во известие тебе, государю, буди: на Олонецкой верфи корабли строятся во всяком поспешании».