Udalbiltza Lizarra Garaziko Itunaren lehen ondorioa izan zen, 1998ko irailean Euskal Alderdi Jertzalea (EAJ), Eusko Alkartasuna (EA), Izquierda Unida/Ezker Batua (IU/EB) eta Euskal Herritarrok (EH) alderdi politikoek, Euskal Herriko hainbat sindikatuk, jazarpenaren aurkako mugimendu ugarik eta bakearen aldeko bi mugimenduek (Elkarri eta Bakea Orain) sinatu zutena. Hainbat helburu zituen, besteak beste, elkarrizketa eta negoziazioan oinarritutako prozesu ireki baten bidez lurraldetasunari, erabakitzeari eta autodeterminazioari buruzko auziak ebaztea, inolako eragilerik kanpoan utzi gabe indarkeriarik gabeko giro batean. Irailaren 18an ETAk komunikatu bat kaleratu zuen aldebakarreko tregua mugagabea iragarriz, eta une horretatik aurrera aurreko helburuak bete ahal izateko testuingurua zabaldu zen.
1999ko otsailean Lizarra-Garazi Ituna sinatu zuten alderdietako zinegotziz (EAJ, EA eta EH, Euskal Herriko udal-kargu gehienak betetzen baitzituzten) osatutako Euskal Herriko Udal-hautetsien Asanblada batean eta herrialde osoko hautetsiak barneratuko zituen udal-erakunde bat sortzea erabaki zen, administrazio-esparru ezberdinak hartuko zituena, hots, Euskal Autonomia Erkidegoa, Nafarroa eta Iparralde. Urte horretako irailean guztira 1778 zinegotziz osatutako Asanblada bat sortu zen (Nafarroako 271 eta Iparraldeko 24 euskaldun), 315 udaletxe ordezkatzen zituena (horietako 57 Nafarroakoak eta 14 Iparraldekoak). Asanblada horrek Udalbiltza izena hartu zuen. Han elkartutako hautetsiek bost helburu ezarri zituzten instituzioarentzat:
- Euskal Herriaren aitorpena sendotzea nazio modura.
- Udal-ordezkarien ekintza itundua zilegitzea, Euskal Herria "komunitate politiko, kulturak, soziologiko eta ekonomiko" gisa definitzen duten lan- eta kolaborazio-esparruak bultzatzea ahalbidetuko lukeena.
- Etorkizunean egituraketa politiko eta instituzionalaren ikerketan eta eztabaidan kolaboratzea.
- Elkarrekin eta modu homogeneoan nazioaren eraikuntzari dagozkion arazo eta erronkei aurre egiteko baliagarri izango den oinarrizko diagnosi bat egitea.
- Nazioartean Euskal Herria berezko eta aparteko nazio gisa agertaraztea eta Europaren eta hartako instituzioen etorkizuneko egituraketan halaxe jarduteko borondatea agertaraztea.
5 jardute-eremu diseinatu ziren, hots, euskara, kultura, lurralde-antolakuntza, hezkuntza, eta garapen ekonomiko eta soziala. Hainbat zinegotziz osatutako Batzorde iraunkor bat eratu zen (EAJko 7, EAko 4, EHko 4 eta Abertzaleen Batasuna Iparraldeko alderdiko zinegotzi bat).
Urte horren amaieran ETAk su-etena hautsi zuen eta Udalbiltza osatzen zuten alderdien artean haustura bat sorrarazi zuen horrek, hala Asanbladaren jarduna eten egin zen 2000. urtera arte. ETA esplizituki kondenatzearen inguruko gatazka sortu zen, EAJ eta EA alderdietako kargudunek halaxe egin zuten, baina EHko zinegotzien jarrera bestelakoa zen, hots kondena ez aipatzearena. 2000. urtearen amaieran lehenengoek Zuzendaritza Kontseilua osatu zuten eta elkarte instrumental bat sortu zuten, Udalbide, Udalbiltzaren proiektuak bereganatu zituena.