Il paese è posto quasi a guardia dell'ampia valle concava in cui scorre il Celone. Esso discende a valle tra i monti, in una cornice maestosa, e riceve le acque del displuvio e delle sorgenti chiacchierine dei monti Perazzone, Vetruscelli e Cornacchia, cioè dei torrenti Foce, Feudo e Freddo.
Il paese, in passato, aveva forma di triangolo isoscele ed era chiuso da una cinta muraria costituita da abitazioni fortificate. Alla base del triangolo si aprivano le due porte, dette del Pozzo e del Piscero. Al vertice del triangolo, più vulnerabile, fu edificato il castello bizantino, del quale resta solo la torre. Solo due, degli originari 3 piani, sono ancora visibili.
Stando ad ipotesi accreditate, la battaglia tra Annibale ed i Romani
del 216 a.C. sarebbe avvenuta non a Canne sull'Ofanto ma nella valle del
Celone, presso Castelluccio Valmaggiore.
Il toponimo deriva
comunque da Castrum Vallis Maioris, che identifica il castrum edificato
dai bizantini al fine di controllare la valle del Celone.
Fin dal 1440 Castelluccio venne annessa alla baronia della Val Maggiore, che comprendeva anche Celle di San Vito e Faeto. La baronia appartenne, nel corso dei secoli, a diversi casati, fra i quali spiccano i Carafa e i Caracciolo, fino agli inizi dell'Ottocento quando, abolito il feudalesimo, il comune riacquistò l'autonomia.
Fino al 1890 il clero di Castelluccio Valmaggiore aveva il diritto di gestire la chiesetta di San Vito, sita in territorio di Faeto lungo il tratturello Camporeale-Foggia che ripercorreva l'antica via Traiana e la medievale via Francigena.