Población antigua identificada con la Andelos de Tolomeo y Andola de los visigodos. Sus habitantes serían los andologeneses, pertenecientes, según Plinio, al convento jurídico de Zaragoza. A comienzos de siglo subsistían, como nos lo da a conocer Altadill, «... a la vista en su jurisdicción y en una leve altura, los restos de un aparentemente castillo romano, y en la misma margen izquierda del citado río (Ega)... se han encontrado varias veces señales abundantes de edificación extensa y notable, no escaseando los residuos cerámicos». En la Edad Media la fortaleza de Andosilla fue ganada a los musulmanes por Alfonso el Batallador, rey de Navarra y Aragón, en la segunda década del siglo XII. Debió ser de poca importancia pues tiene escasas resonancias en la historia de Navarra. Este castillo fue realengo. Altadill registra 10 alcaides en cerca de un siglo. A mediados del siglo IIII era su alcaide Lope González de Andosilla. En 1341 Gil González de Andosilla. En las cuentas del Merino de 1390, consta como abandonado. A los habitantes de este pueblo dio fueros en 1210 el rey Don Sancho el Fuerte, concediéndoles que sólo pagasen de pecha anual 100 cahices de trigo, otra tanta cebada y 600 sueldos, debiéndola entregar en Peralta al clavero del rey; que no fuesen a ninguna labor fuera del término de la villa, sino a las heredades del rey dándoles pan el día que trabajasen; que trabajasen también en la fortificación de las cuevas; que no tuviesen clavero hijo de la villa, y que ningún merino entrase en sus ganados. En 1214 doña Narbona dio a dicho rey todo cuanto tenía en Andosilla y Funes. En 1294, los reyes don Enrique y doña Juana nombran a Pedro Sánchez de Falces para el mando y tenencia de la torre y cuevas de Andosilla. Andosilla fue tomada por los castellanos en la guerra de 1379. En 1366 padeció mucho por la mortandad de ganados, y el rey la socorrió con 100 libras y 24 florines. En 1414 Don Carlos III dio las pechas de este pueblo, y loa homicidios, a Mosen Pierres de Peralta y sus sucesores, a perpetuo en cambio de Berbinzana, que Mosen Pierres dio al rey. En 1495 pertenecía Andosilla al conde de Lerín y tenía 66 vecinos cristianos y II judíos: éstos pagaban dos florines de pecha al año. Los labradores de Andosilla pagaban al rey, en 1511, una pecha de 50 cahices de trigo por el término de Resa, la cual dice que había sido donada a Mosen Pierres de Peralta.