La storia della città ruota attorno al colle della Madonna del Castello, posizione strategica da preferire. Già dal IX secolo comunque l' abitato sembrerebbe configurarsi strutturalmente su due gruppi, il primitivo borgo vallivo, fortificato fino al Conservatorio delle Pentite, e la parte esterna alle mura da identificarsi con la piazzetta di San Giuliano. Il toponimo Castrovillari sembrerebbe infatti derivare da Castrum e Villàre o Castrum Villarum, nell' anno 1064 la città viene assediata e conquistata dai normanni, appare per la prima volta il toponimo Castreville  in un diploma del conte Ruggero( 1094 ). Una notevole ripresa della città di Castrovillari si riscontra intorno al secolo XI  sotto il dominio svevo che ne ampliano i confini tanto da definirla " Città nuova degli Svevi ". La leggenda della costruzione della chiesa, vuole che nell' anno 1090 Ruggero conte di Calabria e di Sicilia successore di Roberto Guiscardo, ordinò per paura di ribellione da parte dei cittadini la costruzione di un castello in cima al colle ai cui fianchi si adagiava l' antica città. Si narra che i lavori iniziarono subito ma da " ignota manu " la mattina seguente si trovava distrutto tutto ciò che il giorno precedente era stato fatto. Pensarono quindi di scavare la terra più in profondità mentre ciò si faceva rinvennero una immagine della Madonna dipinta su un pezzo di muro, il popolo gridò al miracolo ed il " buon " Ruggero invece di far edificare il castello ordinò che in quel luogo venisse costruita una chiesa che fu detta appunto Madonna del Castello. Secondo quanto ci espone il prof. Francesco  Di Vasto in " Storia e Archeologia di Castrovillari ", la chiesa fu detta anche Santa Maria de Castro come scritto in un diploma del 1114 nel quale si fa esplicito riferimento a un diploma del 1109, oggi perduto,che appare il più antico ricordo della chiesa.