Fondato originariamente durante la dominazione araba come fortezza per presidiare la valle del Salso, crollò improvvisamente la notte del 27 febbraio 1567 a seguito di un movimento franoso.
Il castello deve il suo nome al color ocra dei mattoni che rivestivano le sue torri, realizzati in pietra di Sabucina.

Al Castello di Pietrarossa e al nome arabo di Caltanissetta è legata una leggenda, gli antichi storici normanni, infatti, spiegavano il nome arabo della città, - Kalat Nisa - cioé 'Castello delle Donne', riferendosi alla leggenda secondo cui l'emiro di Palermo custodiva le sue donne proprio in questo castello, e le spose in attesa del suo ritorno preparavano vari dolci tra cui una sfoglia fatta essiccare al sole che poi veniva riempita con ricotta fresca: l'antenato del cannolo.

Ma questa storia risulta poco probabile in quanto le caratteristiche costruttive del Castello-Fortezza non rispondevano alle esigenze di un harem, mancavano, poi, giardini, fontane e il luogo era costantemente battuto dai venti ed era evidentemente poco adatto a custodire delle principesse reali.

Il nome di Caltanissetta va spiegato, invece, riferendosi a motivi di tipo socio-economico, visto che la città per la maggior parte dell'anno era abitata solo da donne e bambini, mentre gli uomini erano impegnati nel lavoro in campagna e di rado tornavano al borgo.

Il castello di Pietrarossa venne sempre e solo utilizzato, sia dagli arabi che, successivamente, dagli svevi, a scopi difensivi, e venne destinato, per un breve periodo, ad usi abitativi solo sotto i Moncada, che comunque a causa della sua scomodità lo abbandonarono presto e se ne servirono come prigione.

L'unica rappresentazione che resta tuttora del castello è un quadro del '500 che si trova presso i musei Vaticani e che è servito da ispirazione ad uno dei plastici realizzati dal prof. Santagati ed esposti durante la mostra 'Qal-at-Nisa - il nostro mondo arabo' .
Secondo questo quadro il castello, era costituito da tre torri, e oggi rimangonosolo una parte della torre di difesa e una parte del 'maschio', la parte centrale della fortezza. Il castello è raffigurato in maniera stilizzata anche nello stemma della città.