La prima data certa e l’attuale denominazione risalgono al 1095, anche se qualcuno indica che la fondazione di San Nicandro sia avvenuta nel 663 d.C.
In quell’epoca Lucera fu sconfitta dal’Imperatore Costante II e gli scampati del massacro si rifugiarono su una collinetta, l’attuale “Terra Vecchia”. Qui Federico II costruì un castello nel 1238, forse su dei resti di fortezza normanna o romana. San Nicandro, però, potrebbe avere avuto origini anche dai Longobardi, che arrivarono sul Gargano dopo la sconfitta sul Garigliano nel 915. Il serpente che si trovava sulla sacrestia di Santa Maria del Borgo è di origine Longobarda. I Longobardi del ducato di Benevento, anche dopo essere stati battezzati, continuarono ad adorare il serpente.
Come tutti i paesi della zona, San Nicandro ha conosciuto, nel corso dei secoli, tantissime storie sulle varie dominazioni straniere: normanni, svevi, angioini. Una data sicura è il 1464 quando feudo e castello vennero comprati da Nicola Della Marra, il cui figlio Gianpaolo li perdette per tradimento.
Qualche studioso locale afferma che nel castello di San Nicandro soggiornarono un Imperatore, Federico II, un re, Manfredi e il Papa Celestino V.