Fue reconquistada a los musulmanes por Alfonso el Batallador y donada en el año 1142 por el rey García Ramírez al Hospital de Jerusalén. Consta que en su término existió una fortaleza denominada Torre del Congosto. Según Altadill su torre estuvo situada en un altozano como una más de las fortalezas vigilantes de la línea que guardaba a Navarra de las incursiones aragonesas que durante el siglo XIII menudearon en busca y captación de la ganadería que en abundancia se acubilaban y pastaban en las Bardenas. Para mayores detalles véase una monografía de dicha villa, publicada por el historiador D. Juan P. Esteban Chavarria. Obtuvo privilegios para el goce de la Bardena real en 1664. El lib. llamado dei Chantre citado por Yanguas dice, hablando de la iglesia de Fustiñana, lo que sigue: La iglesia de Fostinyana es de la orden de San Juan, é presienta vicario el prior de Navarra, é el señor bispe confirmalo é comiéndale la cura de las ánimas; et el dicho señor bispe visita la iglesia, et paga la procuracion el prior, et asigna et da las sepulturas, et el señor bispe manda dotar la iglesia segun á el es bien visto; et por facer la cugida de los diezmos del dito lugar á saber es pan, vino, corderos, leguminas, filarzas, mete el señor bispe un cullidor, et el prior otro, et cada uno tiene su llave del granero dó se llega la diezma del pan; é juran en poder del señor bispe, é son pagados de montón los dichos cullidores de su trebajo, é da la mesion que facen durante la cullida é comen en la abadía; é el día de la cuartacion los cuarteadores facen la tacsa de la provision de los dichos cullidores, segun es la dicha cullida, é segun el trebajo que han pasado; é la mesion del dia de la cuartacion facese asi mismo de montón; et de lo que queda há el señor bispe la cuarta parte de todos los diezmos; et en el cuarto há el redecimo el arcidiano, y el arcipreste saca de montón tres cuartos de trigo é tres de ordio antes que se haga la cuartacion, et quedan las tres partes al dicho prior, et paga al vicario el dicho prior de lo que le queda. Según refiere Idoate en Rincones... [t. II, pp. 365 y 366] hacia el año 1353 existían en Fustiñana cuatro cofradías, las de Santa María, San Just, San Blas y Santa Catalina, que disponían de algunos bienes para sufragar sus gastos. Los de la villa se consideraban hidalgos e infanzones, al no existir en ella labradores pecheros. Una sentencia del Consejo Real del 10 de junio de 1536 confirmatoria de otra anterior de Comptos, excluyó a los pastores de Fustiñana y Cabanillas del goce de los pastos y aguas de la guardería de Sancho Abarca, Cascajo y Tres Montes de las Bardenas Reales. Treinta y seis años más tarde vemos, nuevamente, al Consejo Real a la greña con Fustiñana y a propósito de caza y corte de pinos y olivos en la misma zona. Este pueblo hizo ordenanzas para los ganados caballares, yeguas y juramentos en el año 1547. A finales del siglo (1596) el Real Consejo confirmaba el amojonamiento de montes comunes de Tudela, Fustiñana y Cabanillas. En 1664 compró los derechos sobre las Bardenas mediante el pago de 700 ducados, y en 1683 obtuvo el permiso de tener los ganados lanares en ellas hasta el 20 de junio. Refiere Idoate en Rincones... (t. III, p. 3031 que durante la guerra de Sucesión entre Felipe V y el archiduque Carlos, Fustiñana fue asediada en tres ocasiones por las tropas del archiduque, siendo en todas ellas socorrida por las de Tudela. En el tercer asedio los asaltantes lograron entrar en el pueblo, refugiándose los habitantes en la iglesia. Pero al acercarse los tudelanos con sus milicias y cuarenta caballos, las tropas del archiduque huyeron rápidamente. En el año 1705 Felipe V concedió a perpetuidad el aprovechamiento de las Bardenas al monasterio de la Oliva, Tudela, Corella, Ronkal, Salazar, Arguedas, Valtierra, Fustiñana, Cabanillas, Cortes, Buñuel, Cadreita, Milagro, Villafranca, Marcilla, Funes, Peralta, Falces, Caparroso, Santacara, Mélida y Carcastillo. Tudela, Fustiñana y Cabanillas hicieron una concordia sobre comunidad de montes el año 1722 y sobre amojonamiento del ganado enfermo. El de los montes comunes de Tudela, Cabanillas y Fustiñana con los propios de Cabanillas se realizó en 1755 y años siguientes. En el año 1822, en el trienio constitucional, los realistas pretendían hacerse notar, como se desprende del hecho acaecido en Fustiñana en mayo del mismo año, según refiere Idoate en Rincones... [t. II, p. 112]. Una noche picaron la inscripción de la lápida de la Constitución. Inmediatamente el alcalde intentó detener al autor del hecho, pero no fue posible dar con él. Se conformó con informar al juez de Primera Instancia de Tudela de las pesquisas realizadas. En cumplimiento de la ley de desamortización del 1 de mayo de 1855 se vendieron en esta localidad, en 1863, dos trozos de terreno (Ref. R. G. Ch. "La D. C. en N."1