Pierwsza wzmianka o regionie Nachod pochodzi z połowy XI wieku, kiedy to czeski książę Wratysław II podczas swojej wyprawy do Śląska w 1068 roku zorganizował w pobliskim Dobenínie wybory biskupa praskiego. W XI i XII wieku w pobliżu bramy ziemskiej zwanej Branka, w miejscu dzisiejszego Starego Miasta, istniała prawdopodobnie osada strażnicza. Sam zamek i prawdopodobnie również miasto Nachod założył Hron z rodu Načeraticów w połowie XIII wieku. Zamek został zbudowany przy ziemskim szlaku handlowym w pobliżu granicy czesko-kladskiej i dlatego miał duże znaczenie strategiczne. Potomkowie Hrona utrzymywali Náchod do 1321 roku, kiedy to przejął go czeski król Jan Luksemburski, a od niego w 1325 roku Hynek z Dubé. Panowie z Dubé utrzymywali posiadłość do 1367 roku. W 1414 roku Nachod przejął Boček z Kunštátu i Podiebrad, a w 1427 roku, po śmierci swojego ojca Viktorína, odziedziczył go przyszły król czeski Jerzy z Podiebradów. Podczas wojen husyckich zamek trafił w ręce husytów, a jego załoga musiała wielokrotnie odpierać ataki katolickiego Śląska. W 1437 roku zamek i miasto zdobył husyta Jan Kolda ze Žampachu, który stąd organizował wyprawy łupieżcze do Czech i Śląska. wszedł w posiadanie swojego prawowitego dziedzictwa dopiero w 1456 roku, kiedy to zdobył zamek.