Després d'una primera reunió de 666 alcaldes i regidors al cinema Carlos III de Pamplona el febrer de 1999, la institució com tal es va constituir en el palau Euskalduna de Bilbao el 18 de setembre de 1999, amb l'assistència de 1.778 càrrecs electes municipals procedents de les set províncies basques. En aquesta assemblea es va decidir per consens iniciar una nova marxa institucional entorn de cinc principis programàtics que es podien resumir en dos: d'una banda la reivindicació d'Euskal Herria com nació, i a tota la seva ciutadania i a la nació en si com a subjectes de ple dret; i d'altra banda, el foment, a través de la labor institucional de base municipal, de polítiques comunes de desenvolupament entre els municipis de tots els territoris bascos, en honor de cohesionar les polítiques de les diferents províncies en àrees tals com la normalització lingüística, el desenvolupament socioeconòmic, l'organització i planificació territorial, la defensa dels drets democràtics, l'ensenyament, l'esport, el foment cultural, etc.
Es van organitzar els representants municipals en diferents àrees de treball, i van començar a elaborar un Pla de Gestió per a l'any 2000. L'elaboració i aprovació d'aquest pla va ser a càrrec de la primera Comissió Permanent d'Udalbiltza, composta per set representants del Partit Nacionalista Basc (PNB), 3 de Eusko Alkartasuna (EA), 4 d'Euskal Herritarrok (EH) i 1 d'Abertzaleen Batasuna (AB). Va ser una primera etapa molt marcada per la ruptura de la treva per part d'ETA. Malgrat això, el primer pla de gestió d'Udalbiltza es va aprovar a la primavera de 2000. Posteriorment, el distanciament es va fer cada vegada major entre els representants dels diferents partits, així com el desacord entorn del paper que havia d'exercir la nova institució en una nova i difícil conjuntura marcada pel reinicio de les accions armades per part d'ETA. Els electes representants del PNB i d'EA van crear pel seu compte un nou òrgan directiu, el Consell de Direcció, del que van excloure als representants d'Euskal Herritarrok per haver-se abstingut en la votació entorn d'un comunicat "condemnant les accions armades d'ETA".
Dualitat de tendències
Davant aquesta situació de bloqueig, a la tardor de l'any 2000, el Pla de Gestió aprovat a la primavera no havia fructificat, i els compromisos aprovats per Udalbiltza en l'inici de la seva marxa havien quedat tots com a tasques pendents. Va ser per això pel que al voltant de 300 càrrecs electes municipals, la majoria de l'esquerra abertzale, recolzats per diversos independents i representants d'EA i AB, es van reunir de nou a Pamplona per sol·licitar a la Comissió Permanent que "reprengués la seva labor, sense cap mena de discriminació cap a cap representant municipal, i que convoqués una nova Assemblea General que reconduís la situació". Paral·lelament, aquest col·lectiu d'electes municipals va constituir una associació anomenada Udalbiltzaren Alde (A favor d'Udalbiltza), amb l'objectiu que la institució reprengués la feina de casa "per sobre de les diferències entre partits, i cara a afavorir un nou context de pau i democràcia".
Mentrestant, l'organització composta per electes del PNB i EA va mantenir el nom "Udalbiltza", però va començar a utilitzar la denominació "Udalbiltza-Udalbide" o simplement "Udalbide". No va haver-hi resposta cap a les sol·licituds d'Udalbiltzaren Alde. El gener de 2001, es van reunir les signatures de 920 càrrecs electes municipals a favor que es convoqués una Assemblea General d'Udalbiltza. Aquesta assemblea hauria de ratificar els principis programàtics aprovats en setembre de 1999 a l'Euskalduna, i aprovar un pla de Gestió pel 2001 basant-se en l'anteriorment aprovat pel 2000 i que no s'havia vist realitzat. Aquesta assemblea va tenir lloc el 24 de febrer de 2001 en el Palau de Congressos i Auditori Kursaal de Sant Sebastià, i a la mateixa van acudir 780 regidors i alcaldes de tots els territoris bascos.
A partir d'aquest moment es pot parlar de l'existència de dues sensibilitats i dues praxis entorn d'un mateix eix programàtic inicial.
Desenvolupament nacional basc
Basant-se en el finançament a través de partides pressupostàries aprovades en ple pels diferents ajuntaments representats en *Udalbiltza, aquesta va col·laborar amb els més diversos projectes de desenvolupament nacional basc, ben subvencionant projectes d'agents públics o privats de diferents territoris (mitjans de comunicació en euskera, centres d'ensenyament en euskara als territoris francesos, associacions de foment cultural o lingüístic, etc.), o ben promovent com a institució nous projectes. Per exemple: l'elaboració de la primera base de dades estadística que conjuminava les estadístiques de la Comunitat Autònoma Basca, la Comunitat Foral de Navarra, i les dades de les tres províncies d'Iparralde (Euskal Herria datuen talaiatik - Euskal Herria des de l'observatori de les dades); la Declaració de Nacionalitat Basca (Euskal Herriko Naziotasun Aitormena o EHNA), com a document identitari de tramitació voluntària; l'elaboració a través de la implementació de metodologia participativa de la Carta de Drets d'Euskal Herria (amb una carta general de drets civils i polítics, i altres cinc cartes de drets sectorials); o la creació del Fons de Cohesió i Desenvolupament d'Euskal Herria, com a organisme autònom que tenia com a primer objectiu la promoció de nous projectes empresarials i culturals en Zuberoa (el territori més a l'est del país, el menys poblat i el més deprimit econòmicament). Al desembre de 2002 es va celebrar a Sant Sebastià la Conferència pels Drets dels Pobles, promoguda per Udalbiltza, a la qual van acudir més de 150 ponents i representants institucionals i acadèmics dels cinc continents.
Criminalització i suspensió d'activitats
El 29 d'abril de 2003, poc abans de les eleccions municipals, l'Audiència Nacional d'Espanya a través del magistrat instructor Baltasar Garzón va ordenar la detenció i ingrés a la presó de 13 regidors i/o treballadors membres d'Udalbiltza. Així mateix, van precintar les seus de la institució a Pamplona, Bilbao i Astigarraga i van bloquejar els comptes tant del Consorci Udalbiltza (la figura jurídica adoptada per la institució pública) com de l'organisme autònom Euskal Garapen eta Kohesio Fondoa. Es va dictar, a més, la suspensió d'activitats per Udalbiltza. Posteriorment, al maig, es va ordenar l'ingrés a la presó d'altres tres representants d'Udalbiltza (entre ells el president de la institució i llavors alcalde d'Ondarroa), després d'haver estat citats a declarar i haver acudit a l'Audiència Nacional. Al juny detindrien a un altre representant més de la institució, aquest cop a més de labortà de ciutadania francesa. Totes aquestes persones van romandre a la presó fins a abril de 2004. Aquest mateix any es va dictar l'ordre de processament contra un total de 22 membres d'Udalbiltza (els anteriorment empresonats i uns altres més).
Al setembre de 2007, es va aixecar la suspensió d'activitats per Udalbiltza, però tres dies després, el 12 de setembre, es van donar a conèixer les peticions fiscals definitives pels 22 encausats: el ministeri fiscal va sol·licitar 10 anys de presó per delicte d'integració en banda terrorista per a tots ells, i 5 anys més per a quatre dels encausats per un delicte de malversació de fons públics; l'associació Dignitat i Justícia va sol·licitar penes d'entre 15 i 23 anys per les mateixes causes.
Resolució judicial
El judici oral contra Udalbiltza es va dur a terme entre el 15 de juliol i el 26 d'octubre de 2010. Finalment, totes les persones encausades van ser absoltes en sentència de l'Audiència Nacional el 20 de gener de 2011. Segons aquesta sentència, la tesi de l'acusació quedava "reduïda" a la coincidència o adhesió ideològica dels processaments amb "alguns dels objectius polítics que els terroristes proclamen com a justificació de la seva conducta criminal, la qual cosa, per si, no constitueix cap delicte" i "seria suficient per dictar sentència absolutòria", ja que "en un estat democràtic queden fora de l'àmbit penal l'acció política i les opinions i manifestacions ideològiques, agradin o no, siguin majoritàries o minoritàries, siguin compartides o no".[1][2]
