Die erste Erwähnung der Region Náchod stammt aus der Mitte des 11. Jahrhunderts, als der böhmische Fürst Vratislav II. während seines Feldzugs nach Schlesien im Jahr 1068 in der Nähe von Dobenín die Wahl des Prager Bischofs organisierte. Im 11. und 12. Jahrhundert existierte offenbar eine Wachsiedlung in der Nähe des Landtors namens Branka, an der Stelle des heutigen Altstädts. Die Burg selbst und wahrscheinlich auch die Stadt Náchod wurden Mitte des 13. Jahrhunderts von Hron aus dem Geschlecht der Načeratice gegründet. Die Burg wurde an einer Handelsstraße in der Nähe der Grenze zwischen Tschechien und Kladsko erbaut und hatte daher große strategische Bedeutung. Die Nachkommen von Hron hielten Náchod bis 1321, als es der böhmische König Johann von Luxemburg erwarb und 1325 an Hynek von Dubá weitergab. Die Herren von Dubá hielten die Herrschaft bis 1367. Im Jahr 1414 erwarb Boček von Kunštát und Podiebrad Náchod und 1427 erbte es nach dem Tod seines Vaters Viktorín der zukünftige böhmische König Georg von Podiebrad. Während der Hussitenkriege fiel die Burg in die Hände der Hussiten und ihre Besatzung musste daher mehrmals Angriffe aus dem katholischen Schlesien abwehren. Im Jahr 1437 eroberte der Hussit Jan Kolda von Žampach die Burg und die Stadt und unternahm von dort aus Raubzüge nach Böhmen und Schlesien. Georg von Podiebrad trat sein rechtmäßiges Erbe erst 1456 an, als er die Burg eroberte.