Na miejscu tej warowni drewniano-ziemnej powstał następnie zamek murowany. W starszej literaturze jego budowę datowano na lata 1367–1371, jednak początek prac w 1367 roku nie znajduje bezpośredniego potwierdzenia w zachowanych źródłach. Krzysztof Kwiatkowski przyjmuje ostrożniej, że przekształcenie założenia w warownię murowaną nastąpiło zapewne pomiędzy około 1350 a około 1370 rokiem, być może nieco później. Marcel Knyżewski zalicza Szestno do niewielkich wschodniopruskich siedzib niższych urzędników krzyżackich, których zasadniczym elementem był pojedynczy murowany dom zamkowy, dopiero później uzupełniany dalszą zabudową.
Położenie zamku miało znaczenie zarówno administracyjne, jak i komunikacyjne. Warownia znajdowała się na skraju obszaru dawnej Galindii, na przesmyku pomiędzy jeziorami Juno i Salęt, przy szlaku prowadzącym przez kolonizowane tereny w kierunku Kętrzyna. Kwiatkowski wskazuje, że zamek w Szestnie mógł osłaniać jeden z głównych traktów prowadzących z obszaru Wielkiej Puszczy w kierunku Kętrzyna.
Od 1401 roku zamek był siedzibą prokuratora krzyżackiego podległego komturowi Bałgi. Prokuratorzy rezydowali tu nieprzerwanie do sekularyzacji państwa zakonnego w 1525 roku.