Dall’11 novembre 839 al 29 ottobre 940, gran parte del territorio dei monti sicani, fu conquistato dai mussulmani, e dunque anche Castronovo ebbe la stessa sorte. Sotto il dominio degli arabi furono eseguiti i primi lavori di bonifica, iniziarono le pratiche irrigue e furono introdotte nuove culture. L’antico nome “Crastus” divenne, per la trasposizione della lettera “r” , Castrus e quindi Kars-nub per gli arabi, cioè “dai bei dintorni, dalle molte entrate e produzioni del suolo, terre a seminativo, poste tra piccoli torrenti”, fino a divenire Castrum per i normanni. Si deve agli arabi la costruzione di due casali il Rabat (Rabatello), accanto a una ricca sorgente d’acqua ed il Rakal-biat , successivamente ribattezzato come Santa Maria della Bagnara, distrutto da una frana nella metà del settecento.
Al tempo in cui i normanni procedevano alla conquista della Sicilia, Kars-nub era governata dal crudele emiro, Abu-Becher, beco. Questi venne a uno scontro con un mugnaio di nome Aymo de Milatio, il quale, non sopportando l’affronto, si mise d’accordo con i normanni e durante la notte indicò loro un percorso segreto che consentì di calarsi, tramite delle funi, dalla montagna del Kassar all’interno della fortezza araba. Ciò permise la conquista della città senza alcuno spargimento di sangue. Il conte Ruggero fortificò i luoghi conquistati costruendo una fortezza, che dominava la città, accanto al preesistente castello, con il quale comunicava per mezzo di una strada sotterranea. Sul colle di S. Vitale fece erigere una cappella dedicata a San Giorgio, la Chiesa del Giudice Giusto e tanti altri monumenti.
Dopo aver consolidato il potere, il conte Ruggero concesse la signoria della città al fedelissimo Ruggero di Barnavilla, cui succedette il figlio Rinaldo al quale fu in seguito tolta perché aveva partecipato alla rivolta dei baroni contro Guglielmo I.