Amato di Montecassino, nella sua storia dei Normanni, attribuisce a Roberto il Guiscardo la costruzione di Castel Terracena: En lieuz competens fist merveilous palaiz sur li mur de la cité, si que li estoient dedens et defors de la terre.
Anche Guglielmo de Apulia, nella sua opera sulle imprese di Roberto, cita la costruzione di un castello inespugnabile in inferiore situ rispetto al castello longobardo.
Il castello doveva sorgere infatti a ridosso delle mura orientali della città, a sud dell'altura oggi corrispondente al rione comunemente detto dei Mutilati. La scelta del luogo fu sicuramente dettata da esigenze di sicurezza sul piano militare, ma doveva influirvi anche la presenza nelle immediate vicinanze della cattedrale. Si sanciva così, anche sul piano logistico, l'accordo faticosamente raggiunto tra la nuova dinastia regnante e il potere religioso. La posizione decentrata rispetto al resto della città, rispecchiava anche una voluta separazione tra il centro amministrativo e il cuore civile e commerciale, rimasto più a sud nel rione delle Fornelle, intorno alla Curtis Dominica e alla Giudecca.
Il castello fu costruito quindi dopo il 1076, data dell'invasione normanna, e prima della conclusione dell'opera di Amato, tra il 1080 e il 1086. Dai documenti esso risulta essere stato, tra la metà del XII e la metà del XIII secolo, sede della curia angioina di cui è testimonianza una riunione nel 1251. Riccardo di S. Germano ne ricorda un soggiorno di Federico II nel 1255. Nel 1301 il suolo su cui sorgeva la reggia fu donato al monastero di S. Benedetto. E' probabile che il castello sia andato in rovina nel 1275 in seguito ad un forte terremoto che distrusse gran parte della città. Di questo castello oggi affiorano solo poche labili tracce che rendono difficile stabilire con esattezza l'area su cui esso insisteva, anche in assenza di una puntuale indagine archeologica. Scendendo da via S. Michele, attraverso una scala che mette in comunicazione con la via sottostante, si attraversa un piccolo cortile. 
Alzando lo sguardo è possibile riconoscere, sulle pareti dell'edificio che vi si prospetta, forse una torre residua del castello, le decorazioni originarie. Si ritrova infatti quel motivo a tarsia policroma che caratterizza l'architettura salernitana dei secoli XI e XII, presente nell'atrio del Duomo, sugli archi che decorano i portali di Palazzo Fruscione, nella Curia Arcivescovile e in altri episodi minori. Di Castel Terracena ci è pervenuta una testimonianza nel carmen ad honorem Augusti di pietro da Eboli che narra dell'insurrezione dei salernitani contro Costanza D'Altavilla rifuggiatasi nella reggia con le sue guardie. Le miniature che accompagnano il racconto, nel manoscritto conservato nella Biblioteca Civica di Berna, raffigurano il palazzo ai piedi del monte Bonadies, su cui sorgeva il castello detto di Arechi.