Il Castello di Pietrarossa venne costruito su una rocca a picco su un burrone che dominava la vallata fino al fiume Salso.
Le origini del castello sono controverse ma la versione più accreditata vuole che il promontorio dove sorge il castello inizialmente fu abitato dalle popolazioni dei Sicani che abitavano il vicino villaggio, battezzato dagli storici Nissa, dimostrato dalla presenza di simboli dell'alfabeto sicano. Nel VII secolo a.C. vi si stanziarono i siracusani e il promontorio fu infruttuosamente attaccato dagli ateniesi. Sembra che i romani, dopo la seconda guerra punica, lo abbiano utilizzato come fabbrica, prima che cadesse nelle mani degli Ostrogoti. Ma il nucleo vero e proprio del castello fu edificato dai bizantini tra il 750 e l'800. Il Castello infine cadde in mano araba che lo ribattezzarono Qalat-an-Nisa.
Nel 1086 Ruggero conquista Caltanissetta, roccaforte musulmana tradotto nella nostra lingua in castra foeminarum.
Da Idrisi nel 1150 ca. Qal'at an-Nisa è ricordata come "rocca di bella costruzione".
Nel 1282 il castello sarà saccheggiato durante la guerra del Vespro e nello stesso anno Pietro d'Aragona nomina Bernardo de Sarrià castellano di Caltanissetta dopo la rimozione di Ruggiero Barresi.
Durante il periodo aragonese il castello raggiunse il massimo del suo prestigio, essendo stato scelto come sede di tre Parlamenti generali siciliani: nel 1295, quando vi si volse il convegno dei baroni di Sicilia; nel 1361, quando Federico III vi si rifugiò per sfuggire alla morsa dei baroni siciliani; nel 1378, quando, alla morte di Federico III, vi si riunirono i quattro Vicari per spartirsi il governo dell’Isola.
Nel 1407 il castello venne concesso in feudo da re Martino a Matteo II Moncada e ai suoi eredi, nelle mani dei quali rimase fino alla soppressione del Feudalesimo.
Nella notte del 27 Febbraio 1567, forse per una scossa di terremoto, il castello crollò. Rimasero in piedi solo un muro diroccato, una torre di guardia in pietra viva, terrapieni, bastioni ed un ponte di comunicazione.
Da un elenco di spese effettuate per conto del principe Moncada del 1591 si
evince che parte del castello viene conservata con lavori di manutenzione e che contemporaneamente però inizia l'utilizzo della rocca come cava di pietra da costruzione.
Nel corso del XVII secolo continuerà la demolizione del castello, parzialmente crollato. La pietra verrà utilizzata per le principali costruzioni dell'epoca e nel 1827 il decurionato di Caltanissetta delibera che per la costruzione della via del Monastero di Santa Croce la pietra dovrà "sbarbicarsi e tagliarsi dalla parte meridionale del castello di Pietrarossa".

Il castello, ubicato al margine orientale del centro storico di Caltanissetta, si erge su una serra calcarea e sfruttando la morfologia del terreno si affaccia sulla valle del fiume Salso. Situato all'estremità inferiore del quartiere Angeli, primo nucleo dell'attuale abitato urbano di Caltanissetta, era accessibile, attraverso un ripido percorso, esclusivamente dal fronte rivolto verso la città. La sua posizione geografica consentiva il controllo di un'importante via di comunicazione intema, qual era il fiume Salso, ed il collegamento visivo con il castello di Pietraperzia.
Adibito esclusivamente a funzioni militari, inadeguato come residenza nobiliare, decadde rapidamente con l'avvento dei Moncada, responsabili del successivo abbandono.
Il castello deve il suo nome al tipo di pietra usata per la costruzione, parte della quale è ancora visibile, riutilizzata, nella muratura dell'attiguo convento dei padri Riformati.

Nel linguaggio popolare è denominato murra di l'Anciuli, con un chiaro riferimento alla limitrofa chiesa di Santa Maria degli Angeli ed al materiale usato poiché il termine murra, nel dialetto siciliano, individua sabbia o pietra rossa.
Planimetricamente articolato su vari livelli, risultava costituito da tré torri collegate da cortine murarie, delle quali oggi risultano visibili resti di quella alta circa 25 metri, e della torre di vedetta nord.
La grande torre centrale è costruita su una roccia bipartita da una profonda fenditura che la attraversa longitudinalmente.
Nel lato sud, a cavallo della fenditura, sono visibili una feritoia in pietra da taglio ed inferiormente un'apertura con arco a sesto acuto privo del concio di chiave, presumibilmente preceduta da una scala d'accesso esterna oggi non più esistente.
Il fianco sud-ovest è rinforzato da un cantonale in pietra da taglio, probabilmente eseguito nel XVI secolo dopo un parziale crollo della parte superiore della torre; tale tesi è supportata dall'esistenza nel cantonale di conci tagliati a sguincio, facenti parte in origine di una finestra ubicata in sommità, lato ovest, della quale restano solo il davanzale ed uno stipite.
In cima alla torre è posizionata una cisterna per liquidi rivestita con intonaco che ingloba frammenti ceramici di invetriate piombifere verdi a decorazione solcata e invetriate a decorazione dipinta, databili tra la fine del XII secolo ed i primi del XIII.
Ai piedi della torre, nell'area dello sperone, lo scavo delle murature parzialmente interrate ha portato alla luce un ambiente la cui esatta consistenza non è individuabile a causa del crollo della parete ovest, dovuto all'utilizzo della rocca come cava da costruzione.
Lo scavo in tale area ha consentito il rinvenimento di ceramica da fuoco che testimonia una fase abitativa del XIII secolo.
Alla fine del percorso d'accesso al castello, resti di murature addossate alla roccia fanno pensare all'originaria presenza di ambienti di servizio coperti con strutture lignee; poco distante è sita una profonda ed ampia cisterna intonacata, interamente interrata.
Ciò che resta dell’antico castello è ora proprietà comunale, insieme alla Chiesa di S. Maria degli Angeli, costruita nel XIII secolo, seconda parrocchia della città dopo Santo Spirito.