Les restes romanes properes a la vila fan pensar que, encara que es desconeix l'any de la seva fundació, podria estar relacionada amb el moviment d'algun petit assentament romà proper a posicions més defensives davant els atacs bàrbars.
La zona de Sádaba començà a repoblar-se al segle xi. El 1099 foren els seus senyors García Garcés y la seva esposa Blanquita (o Velasquita). El 1125 es construí un castell més primitiu que l'actual, fundat per Alfons I El Batallador. El 1159 era propietat d'un fill dels senyors, Don Pedro García, la qual cosa significava un senyoratge hereditari, quelcom res comú a Aragó durant el segle xii.
Als inicis del segle xiii Arnau d'Alascún tiranitzava els veïns de Sádaba i realitzava corregudes per la contigua Navarra, per la que Sanç VII "El Fort" actuà militarment contra ell i posà a Sádaba sota la seva protecció el 1215. El 1221, hagué de repetir l'operació contra el fill de l'anterior, Fortanet d'Alascún, la seva mare Maria, els quals lliuraren la vila a perpetuïtat.
El 1223 ja figurava Ferran de Leret com a tinent a “Sádaba Nova”, any del qual data el castell nou. El seu successor Teobald I tornà la vila i el castell a Fortanet el 1244, a precs del comte de Verán, però amb totes les obligacions d'un vassall. Sádaba tornà a Aragó per sol·licitud dels seus veïns el 1261. Anys després s'aixecà en armes per la guerra contra Navarra i França el 1283.
A la Guerra dels dos Peres, Sádaba fou una de les lliurades en ostatges a Carles II de Navarra durant les negociacions entre ambdós reis. Pere IV vengué la vila a Francisco de Villanueva el 1384, però els veïns compraren llur llibertat el 1399 i Sádaba ja no tornà a sortir de la Corona d'Aragó. El 1452 tornà a patir atacs navarresos, igual que altres localitats frontereres. El 1518 Carles I confirma tots els privilegis de la Vila.
.svg)
.svg)
