El cercano yacimiento romano de los Bañales es uno de los principales focos arqueológicos de Aragón, pero las legiones romanas no se establecieron en Uncastillo. La villa la fundó Sancho Garcés I de Navarra en el siglo X, para defender sus territorios de los reiterados ataques de los musulmanes. De esa época data el castillo, que es el edificio más antiguo de la población y ocupa la parte superior de una peña muy escarpada y ceñida por los ríos Riguel y Cadenas, que hacían las veces de fosos.
Unum Castrum, como se llamaba la población en la Edad Media, pasó a pertenecer al reino de Aragón en el siglo XI y tuvo desde entonces un gran valor estratégico como baluarte en la línea fronteriza con Navarra. En el siglo XII, la villa unió a su papel defensivo una gran importancia como lugar de paso en una de las vías secundarias hacia Santiago de Compostela. Casi todos los peregrinos se detenían en la iglesia románica de Santa María, con claustro y coro del siglo XVI, que todavía conserva su pasado esplendor arquitectónico y escultórico. Tal vez los peregrinos se proveían ya por entonces de las morcillas, los chorizos, las longanizas y los quesos que siguen haciendo las delicias de los visitantes de nuestros días.
Los siglos de apogeo del Camino de Santiago fueron también los de mayor esplendor de Uncastillo. En ellos se forjó el aspecto medieval de las calles de la villa y se construyeron las numerosas mansiones señoriales de piedra con recios portones y grandes escudos que se descubren por todas partes. Por entonces se amplió también el castillo con la torre del homenaje (siglo XIII) y el palacio de Pedro IV, donde este monarca aragonés firmó en 1363 con Carlos II de Navarra un pacto defensivo frente a Castilla. De la importancia que tuvo la población para los reyes de Aragón da testimonio también el palacio gótico de Martín el Humano. El momento culminante de la historia local fue el siglo XVI, cuando la villa contaba con palacio de Justicia (la actual casa consistorial) y con una lonja de la que quedan restos en la plaza del Mercado. Este magnífico entorno sirve de marco a las hogueras de la víspera de san Sebastián (19 de enero), los carnavales (febrero) y las auroras de los domingos de octubre, cuando grupos de cantantes animan las calles con sus melodías.
La participación de la localidad en la guerra de Sucesión española le valió en 1708 que Felipe V le otorgara el título de Villa Fidelísima.