Son nom d’origine en basque, Lizarra (tierre de fresnes) indique l’abondance antique de cet arbre sur les berges des méandres de l’Ega. Son nom castillan Estella (issu du latin stella) est du à la volonté de la signaler comme un point significatif du Chemin de Saint Jacques de Compostelle. L’étoile à huit pointes de ses premiers édifices et de ses armes s’est conservée.
Le lieu entre dans l’histoire lorsque Sancho Garces I le reconquit des musulmans en 904. En 1090, Sancho Ramirez y fonde un bourg de francs pour servir les pèlerins européens sur le Chemin de Saint Jacques. Ils durent bien remplir leurs fonctions puisque en 1140, l’éxigent Aymeric Picaud dans son liber peregrinationis déclare : «Estella est une ville dont le pain est bon, le vin excellent, bien pourvue de viande, de poissons et de toutes sortes de bonheurs».
Dans le bourg ou quartier de San Pedro de Rua il y eut depuis des dates très lointaines un important quartier juif (le troisième en importance de Navarre). De fait, les habitants d´Estella étaient traités de «juifs» dans la région, de par l’importance de cette population dans la ville au Moyen Age. Le fait de célébrer un marché sur l’autre rive de la rivière le jour de la Saint Michel provoqua l’édification du bourg de San Miguel. Sancho VI le Sage, fonda le bourg de San Juan pour gens de toutes conditions sociales en 1187. Les minorités jouissaient d’une situation excellente, les juifs et les francs avaient des droits supérieurs à ceux des serfs navarrais chrétiens. Ce fait fut un des points d’origine du massacre des juifs du 6 mars 1328.
En 1512 eut lieu l’invasion de l’armée castillane menée par le duc d’Alba. La population se rendit, mais le Château, défendu par Juan Velaz de Medrano, résista jusqu’à ce que une partie de la population de la ville (le parti des Agramontais) se souleva contre les castillans et les chassa de la ville. Quelques semaines plus tard, les villageois partisans des Béamonteses (et des castillans) leur rouvrirent les portes de la muraille et ils réoccupèrent la ville mettant le siège au château qui se rendit enfin le 31 octobre. Le roi Fernando le Catholique y laissa une garnison importante et fit fortifier la ville en 1520, ce qui n’empècha pas les «Agramonteses» de se rebeller en 1521 et en 1547.
Le 14 novembre 1833, les principaux militaires qui appuyaient les droits dynastiques de l’infant Carlos de Bourbon se réunirent à Estella désignant comme commandant en chef des insurgés le général Tomas Zumalacarregui. La ville devint un bastion carliste jusqu’à l’été 1839, quand le général Maroto pactisa le « Abrazo de Vergara« , juste quelques mois après avoir fait fusiller à « Estella » les généraux qui refusaient de négocier.
Au début de la dernière guerre carliste de 1872, la garnison gouvernementale et les volontaires libéraux contrôlèrent la ville depuis le fort de San Francisco jusqu’à ce que le général carliste Dorregaray vint les assièger en juillet de l’année suivante. Après un siège dramatique ils reçurent le secours de l’armée mais quelques semaines plus tard, les carlistes revinrent à l’attaque et gagnèrent. Pendant deux ans et demi à Estella s’organisa la bureaucratie d’un Etat Carliste en formation, vivant dans la ville les fonctionnaires de Guerre, de Justice, des Finances, et des Affaires Etrangères.
Le 14 juin 1931, un grand nombre de maires des partis carlistes, nationalistes basques et même de droite, se réunirent à Estella, se déclarant favorables à un Statut d’Autonomie dont le brouillon avait été élaboré par des experts de la Société des Etudes Basques (Eusko Ikaskuntza). L’initiative n’eut pas de suites, mais elle sema un précédent important dans l’histoire d´Estella.
En 1936, Estella était gouvernée par un maire nationaliste basque (Fortunato Aguirre) qui prévint le gouvernement de Madrid des détails du soulèvement. Pour cela, le 16 juillet, se réunirent au monastère de Irache le général Batet (envoyé par le Gouvernement) et le général Mola (chef des conspirateurs.) Celui ci fit le serment solennel, donnant sa parole d’honneur qu’il était totalement loyal à la Seconde République. Deux jours plus tard se produisait le soulèvement, et Batet comme le maire furent fusillés par les rebelles.
Petite Place de San Francisco au debut du XX Siècle.
Le 12 septembre 1998, les représentants de six partis, sept syndicats et neuf organisations sociales de tout le spectre nationaliste basque signèrent le «Pacte d’Estella» dans le but de créer un dialogue pour en terminer avec la violence comme chemin pour l’indépendance du reste de l’Espagne. Ce pacte permit à l’organisation terroriste ETA de déclarer une trêve et d’effectuent des négociations, mais sans résultats alors.