Współczesne badania archeologiczne nie potwierdziły jednak, by na tradycyjnie wskazywanej łące, zwanej później Herrenpfeil, faktycznie miał stać zamek. Nie ma również dowodów archeologicznych na, postulowaną przez niektórych autorów, ciągłość między zamkiem i wyrosłą wokół niego osadą w Elblągu a wczesnośredniowiecznym emporium handlowym Truso.
W każdym razie już w 1238 roku niedaleko od fortecy miał powstać klasztor dominikanów, a w latach 1239–1240 rozpoczęła się budowa nowego zamku, tym razem z cegły i z kamienia. Prace nad murowaną twierdzą trwały do roku 1242 lub też do 1260. Elbląg miał stać się rezydencją wielkiego mistrza zakonu krzyżackiego, wobec czego zaplanowano również budowę ogromnego jak na owe czasy kościoła św. Andrzeja, wspartego o romańskie kolumny. W kościele znalazły się relikwie Krzyża Prawdziwego, podarowane w roku 1232 Hermannowi von Salza przez cesarza rzymskiego (w dziewięć lat później papież Grzegorz IX przyznał dziesięciodniowy odpust zupełny każdemu krzyżowcowi, który odwiedzi relikwie krzyża na elbląskim zamku). Cywilne podgrodzie jeszcze w 1240 roku miało otrzymać prawo lubeckie, jednak jego zatwierdzenie przez zakon nastąpiło dopiero w sześć lat później.