Castelnuovo della Daunia

Nome originario del paese fu Castrum Sclavorum o Castelluccio de' Sclavis, in quanto fu fondato dagli Schiavoni, popolazioni slave che, provenendo dall'Illiria (l'attuale Dalmazia, nella penisola balcanica), approdarono sulle coste pugliesi in tre ondate successive nel 642, nell'871 e nel 926. Spingendosi nell'interno in scorrerie banditesche, alcuni gruppi di Schiavoni raggiunsero la zona di Castelnuovo, coabitando pacificamente con una comunità italo-greca già presente sul posto. Da quella fusione nacque l'abitato, uno dei tanti borghi fortificati da mura (castra), edificati in quei frangenti sui colli del Subappennino.
Agli inizi del XII secolo il paese era del conte Roberto II di Loritello (Rotello), che, nel 1118, lo donò con altri suoi beni al vescovo di Bovino. Nel 1187 appartenne a Guglielmo Borrello, mentre è incerta la notizia che i Lombardo, Conti di Troia e di Gambatesa ebbero il paese intorno al 1200.
Verso la metà del XII secolo il paese appartenne al normanno Ruggero de Parisio, cui si deve probabilmente la costruzione del palazzo baronale (oggi sede del Municipio) in cui ancora oggi è presente un'epigrafe del periodo.
Per certo sappiamo che Castelnuovo fu feudo dei De Parisio fino al 1268, prima sotto Ruggero, poi sotto suo figlio Guglielmo ribelle contro Carlo I d'Angiò. Castelnuovo fu poi assegnata nel 1269 a Giovanni Bertaldo (Jean Britaud), Vicario dell'angioino in Toscana.