Medinė pilis piliakalnyje buvo pastatyta Rusios kunigaikščių XI a. XIII a. viduryje Naugardukas buvo prijungtas prie Lietuvos ir valdomas Vaišalgo (Vaišelgos), karaliaus Mindaugo sūnaus. Nors daugelis baltarusių tiki, kad Naugardukas buvo pirmoji Lietuvos Didžiosios Kunigaikštystės sostinė ir Mindaugo karūnavimo vieta (1253 m.), ši nuomonė paremta tik Motiejaus Stryjkovskio Kronika (1582 m.) ir neturi jokio pagrindo vienalaikiuose šaltiniuose. Mūrinė pilis buvo pastatyta Vytauto valdymo metais (1392-1430)