Sulla esistenza di Castelluccio in epoca pre-romana non esistono notizie certe e documentate.

Si sa, pero, che nel suo territorio, in località Sterparo ai confini con l'agro di Bovino, sorgeva in epoca remotissima un importantissimo luogo di culto, testimoniato dal ritrovamento di numerose Stele (lastre di pietra infitte nel terreno, decorate con figure stilizzate femminili o maschili), alcune delle quali sono custodite nel Museo civico di Bovino.

In epoca romana, invece, qualche studioso ritiene di identificare il paese con "l' oppidolum" (villaggio) di cui parla il grande poeta Orazio (65-8 a.c.) nella sua Quinta Satira.
Orazio era solito fermavisi per passare la notte nel corso dei suoi viaggi da Roma a Brindisi (dove si imbarcava per la Grecia e viceversa) .Detto villaggio era attraversato dalla via Appia ed era conosciuto per la fonte di Maggio. Il grande poeta latino afferma che le acque di questa fonte, dopo le piogge invernali era al massimo della sua resa nel mese di Maggio, erano quasi miracolose per chi soffriva di dolori al corpo e all'addome.

Chi ne soffriva, infatti, dopo aver bevuto l'acqua di questo oppidulum" avvertiva presto leggerezza e riacquistava il benessere, Anche il pane con quest'acqua acquistava pregio.
All'inizio della loro conquista (intorno all'anno mille), che culminò con l'unificazione dell'Italia meridionale ad opera di Ruggero II , i signori Normanni (uomini del Nord), costruirono dei "castra" piccoli insediamenti rurali fortificati,che furono numerosi sulle colline subappenniniche. Tali insediamenti miravano in primo luogo a raggruppare i contadini per la coltivazione e la valorizzazione del territorio e anche per fornire al potere signorile, di natura innanzitutto militare, un base fortificata.

Quando i Normanni conquistarono insediamenti di origine bizantina ( e Castelluccio doveva essere uno di questi per via del "Saurorum" (dei Sauri) probabilmente ripopolato da un nucleo di cavalleria Isaurica (dal nome dell'imperatore bizantino Leone III, l'Isaurico), sono ancora presenti ed hanno questa origine). ll primo documento certo l'esistenza del paese risale al 1118, anno in cui il conte Roberto II di Loretello (umile borgo del Molise) ne fece dono al Capitolo della Chiesa di Bovino. Sotto la dominazione sveva di Federico II, il paese divenne una "masseria" regia (unità produttiva agro pastorale).
Dopo la morte di Federico II e la fine della sua dinastia, nel 12 73 il feudo di Castelluccio dei Sauri venne assegnato ad Ugo di Brienne, conte di Lecce e duca di Atene. Nel 1324 il re Roberto d'Angiò riconferma al Capitolo Bovinese la donazione del Casale di Castelluccio degli Schiavi. A partire dal 1390 il paese entra in una fase di declino, che lo porterà al completo spopolamento nel periodo che va dal 1415 al 1446. In seguito, come abbiamo già detto fu ripopolato da 60 famiglie di Albanesi e ritornò così a vivere, anche se nel 1549 per via della natura violenta dei suoi abitanti, su ordine del vicerè Pietro di Toledo, il casale fu fatto bruciare insieme ad altri.

Gli Albanesi portarono con si il rito greco-ortodosso, praticato nella chiesa di San Giorgio (probabilmente l'attuale cappella di San Gerardo), mentre gli abitanti del posto si recavano presso la chiesa di Santa Maria (probabilmente una cappella preesistente alla attuale chiesa della Madonna delle Grazje). Nel 1564 Giovanni Guevara, signore di Bovino, acquista il feudo di Castelluccio dei Sauri dalle mani di Fabrizio Mormile, che così fa parte dello Stato feudale dei Guevara fino al 1860 data della nascita del Regno d'Italia.

Nel primo decennio del secolo il paese era molto diverso. Infatti, le strade non erano asfaltate e c'era pochissimo traffico: le auto erano quasi inesistenti: i carri erano trainati dai cavalli, pochissime biciclette, tanti asini e muli. I pedoni potevano chiacchierare e passeggiare tranquillamente lungo le strade. Le case erano povere, a un solo piano; c'era molto spazio per i giochi dei bambini. I negozi erano pochi e le comodità scarse. Per l'istruzione c'era solo la scuola elementare, dopo scoppiarono le guerre mondiali, nel corso delle quali moltissimi soldati morirono o furono dichiarati dispersi. Quelli che tornarono rividero un paese distrutto con tanta miseria e povertà Per questo motivo, molti decisero di partire in cerca di lavoro. Ci fu l'emigrazione in America, in Germania, in Svizzera, a Milano, a Torino e a Prato. Il paese si svuotò di colpo.

Ma, dopo pochi anni cominciarono a costruire case a più piani, strade asfaltate, scuole nuove, edifici pubblici e tanti negozi. Gli emigranti mandavano i loro risparmi e nel paese tutti cominciarono a vivere meglio, tutti fecero qualcosa per rendere la cittadina più bella e più accogliente. Purtroppo dopo qualche anno e precisamente il 23 Novembre 1980, ci fu il terremoto.

Tutti gli edifici più antichi subirono danni; anche la chiesa parrocchiale di San Salvatore fu chiusa perché dichiarata pericolante Subito dopo però cominciò la ricostruzione del paese: molte case sono state ricostruite, altre ristrutturate; è stata rifatta la piazza, spostato il monumento dei caduti, sono stati costruiti dei grossi condomini a più piani, la scuola materna statale e la scuola media hanno avuto propri edifici, è stato costruito un nuovo municipio e ristrutturato il vecchio. Ora c'è anche una banca, il campo sportivo, il campo da tennis, un bel boschetto, il poliambulatorio, il giardino dei bambini.
Inoltre l' 8 Agosto 1992 è stata riaperta al culto la chiesa di S.S. Salvatore e nel maggio 1994 è stato inaugurato l'Ippodromo , un immenso impianto che si estende su una superficie di quarantacinque ettari, con un parco gioco per bambini, un ristornate e ampio parcheggio.