La forteresse, qui a précédé la ville de plusieurs siècles, a d'abord été un fortin en bois nommé Orechek (ou Orekhov), construit en 1323 par le grand prince Iouri de Moscou (en sa qualité de prince de Novgorod), au nom de la République de Novgorod. Elle défendait les approches de Novgorod au nord et l'accès à la mer Baltique. La forteresse est située sur l'île d'Orekhovets, dont le nom fait référence au mot en suédois, finnois (Pähkinäsaari, littéralement ) et russe.