В 1352 году на пепелище старой крепости новгородцы «заложиша град камен» — так и возникла на Ореховом острове многобашенная каменная твердыня могущественного Новгорода. Общая длина первоначальной стены составляла не менее 350 метров и защищала она наиболее возвышенную часть острова. Возводили ее из крупных и мелких валунов на известковом растворе с лицевыми прикладками плитняка. Перед крепостью, как предполагают исследователи, пролегал ров, который делил остров на две части. В 1430 году берега его облицевали трехстенными срубами, над которыми проходила мостовая с балюстрадой.
Впоследствии укрепления Орешка оказались под землей, хотя и не были разрушены. А произошло это потому, что в оборонительном строительстве в связи с применением огнестрельного оружия произошли большие изменения, и все прежние укрепления строители сровняли с землей. Не стали даже использовать камни-валуны, на смену которым пришел плитняк.
В 1411 году шведы вновь неожиданно появились под стенами Орешка и после нескольких приступов захватили крепость. Они перестроили ее, и потому стены и башни крепости не были похожи на кремлевские строения Древней Руси. Впоследствии Орешек еще несколько раз переходил из рук в руки, но шведы упорно стремились овладеть им.
Постоянная опасность осады и соседство с воинственной Швецией требовали присутствия в Орешке более сильного гарнизона, крепких стен и высоких башен с орудиями. Поэтому новгородцы опоясали крепость каменной оградой, поставили 5 круглых башен, насыпали новый вал и вырыли ров. Островок превратился в каменный замок, со всех сторон омываемый водой, и действительно стал неприступной опорой русского владычества на севере.
Когда Иван Грозный завоевал и разорил Великий Новгород, к Москве отошел и Орешек. Выстроенная в эпоху Московского государства крепость затмила свою новгородскую предшественницу. Высокие военные качества новой твердыни изумляли и друзей, и врагов: когда шведы осматривали новые укрепления, они поняли, что крепость «нельзя ни обстрелять, ни взять штурмом из-за ее мощных укреплений и сильного течения реки». Однако в 1667 году не завоеванный, а отданный по Столбовскому договору Орешек снова перешел к Швеции и стал Нотебургом. Шведы еще больше укрепили теперь уже свою крепость, построили в ней внутреннюю цитадель, которая потом стала известна под названием «Секретного дома».
Петр I называл Нотебург «изрядной и неприступной крепостью», но тем не менее решил завоевать ее, так как она предопределяла дальнейшее освобождение от шведов всей Ингерманландии. Для защиты Нотебурга у шведов находилась на Ладоге хорошо вооруженная эскадра под командованием генерала Нумерса. У Петра I в 1702 году морских сил не было, поэтому он планировал напасть на крепость зимой, не беря с собой осадной артиллерии. Но зима 1702 года стояла необычайно теплая, следовательно, пути к Нотебургу не было, и поэтому составленный план пришлось отменить.
Новое завоевание Нотебурга началось осенью 1702 года. С 1 по 11 октября крепость подвергалась непрерывному бомбардированию, кроме того, по Неве и Ладожскому озеру ее окружала целая флотилия судов и лодок. «Жестокий штурм» начался 11 октября: после 13-часового приступа гарнизон крепости понес огромные потери, и «пылкий Шлиппенбах» сдал Нотебург. При сдаче комендант, по обычаю того времени, поднес Петру I ключ от крепостных ворот, и русский царь повелел прибить его над входом в западную башню, которая впоследствии была названа Государевой. После этого решили не возобновлять старое название «Орешек», а назвать завоеванную крепость Шлиссельбург — Город ключа, так как после ее взятия истоки Невы вновь оказались русскими.
Петр I задумал разместить в Шлиссельбурге тыловую военно-административную и правительственную резиденцию. Осуществил замыслы русского царя архитектор Д. Трезини, который выстроил в крепости ансамбль деревянных домов и 40-метровый шпиль Часовой башни, изменившей силуэт укрепления. Круглые башни крепости были снижены почти до уровня стен, бойницы заложены камнями, ров цитадели засыпан. Над входной четырехугольной башней появилась надпись «Государева», а над ней — черный двуглавый орел и ключ — гербы государства и крепости. На этом боевая история крепости на время закончилась, и началась мрачная повесть превращения ее в государственную тюрьму.
С завоеванием Озерной области и возведением Петропавловской крепости военное значение Шлиссельбурга постепенно сошло на «нет», зато крепость стала идеальным местом, чтобы в ней надежно спрятать и вместе с тем держать недалеко врага или соперника. Но так как тюремных зданий в ней не было, заключенных размещали в солдатской казарме, а также в не сохранившихся до нашего времени доме Меншикова и Государевом доме.