Gród zostaje odbudowany dopiero w połowie XII w. z ponowną fortyfikacją terenu i budową wieży pośrodku oraz dwóch wałów podgrodzia. Położenie grodu wskazuje wyraźnie na jego charakter obronny. Od północnego wschodu zabezpiecza go nie tylko rzeka Narew, ale także szeroka i bagnista jej dolina. Pozostałością po grodzisku jest tzw. Góra Królowej Bony. Do dziś zachowały się tam pozostałości wałów ziemnych otaczających gród.
Na sąsiednim wzniesieniu zwanym Wzgórzem Świętego Wawrzyńca miał stać kościół parafialny wybudowany, według Kroniki Spengeberga, przez świętego Brunona z Kwerfurtu, około 1000 roku. Święty ten, niosąc wiarę chrześcijańską pogańskim ludom na pograniczu prusko-jaćwieskim, poniósł męczeńską śmierć w 1009 r. zaledwie 20 km na wschód od tego miejsca, w okolicach dzisiejszej Wizny. Prawdziwości tej legendy dowodzą wykopaliska archeologiczne, przeprowadzone na wzgórzu. Potwierdzają one, że w tym miejscu stał pierwszy kościół chrześcijański na Północnym Mazowszu. W krypcie odnaleziono wczesnośredniowieczne szczątki bogato ubranego duchownego.
W tym okresie powstał również kościół św. Piotra, który był umiejscowiony na terenie wsi Stara Łomża. Według ww.