En las elecciones del 14 de marzo de 2004, el inesperado triunfo del PSOE tras los terribles atentados del integrismo islámico del día 11 de ese mes, dio un vuelco a la situación. Batasuna siguió estando fuera de la ley pero actuando públicamente.
De esta forma, el 14 de noviembre de ese año (2004), Batasuna planteó en el velódromo donostiarra de Anoeta un proceso de negociación que culminaría con una consulta popular sin violencia. Se comprometía a defender "la utilización de vías exclusivamente políticas y democráticas", pero, no pedía a ETA que dejara las armas, como reclamaban insistentemente todos los partidos. La propuesta, titulada Orain herria. Orain bakea (Ahora el pueblo. Ahora la paz), contemplaba dos mesas de acuerdo: una formada por "todos" los partidos para lograr un acuerdo político refrendado por los vascos, y otra, integrada por ETA y representantes del gobierno de Francia y España, que abordara exclusivamente la desmilitarización y el papel de presos y víctimas.
El portavoz de Batasuna, Arnaldo Otegi, fue el encargado de exponer la iniciativa en una coyuntura marcada por las próximas elecciones vascas, de las que Batasuna iba a quedar fuera dada su situación de ilegalización y, consecuentemente, fuera de todas las instituciones. En el nuevo documento la palabra autodeterminación cede protagonismo a términos como "consulta popular" o "respeto a la decisión de los vascos". Otegi aseguró que Batasuna aceptaría el resultado de un referéndum "vaya en la dirección que vaya", así como la "actual realidad" administrativa de Euskal Herria, compuesta por la Comunidad Autónoma Vasca, la Comunidad Foral Navarra y el País Vasco francés.