Delle vicende costruttive del Palazzo in epoca altomedievale mancano segni chiaramente leggibili, ma sappiamo che alla fine dell'XI secolo, in età già comunale, presso la porta ripresero le funzioni di controllo e fiscali e che all'esterno delle mura si rende necessario costruire dei baraccamenti. Testimonianze di questo periodo storico si trovano oggi rese negli ambienti interrati del Museo, un tempo adibiti a magazzino: un nucleo di sculture provenienti dal territorio piemontese e ad una serie di frammenti, che documentano l'arredo dell'antica chiesa di San Salvatore, edificio esistente nel sito dell'attuale Duomo di Torino.
La storia dell'edificio al centro di piazza Castello comincia in età romana. Sulle fondamenta dell'odierno palazzo si apriva uno degli antichi accessi alla città di Augusta Taurinorum: si tratta della porta orientale, formata da due torri di sedici lati, che incorniciavano quattro ingressi ad arco, due centrali per i carri e due laterali per i pedoni. Le sue dimensioni e la sua forma erano simili a quelle della Porta Palatina a nord della città. Avviandosi verso la Libreria e l'uscita, i visitatori del museo passano attraverso i resti ancora visibili del muro romano.
