Pren el nom de la paraula basca que significa ‘néixer’ o ‘brotar’. La seva creació fou la resposta dels sectors independentistes abertzales per a dotar-se d’una formació política legalitzada, després dels processos d’il·legalització iniciats amb Batasuna. Els estatuts de la nova formació promouen ''la constitució d’un Estat Basc en el marc europeu'' per mitjà de la confrontació exclusivament política i democràtica, i per primer cop es rebutjava explícitament l’ús de la violència.
Malgrat això, al març del 2011, la Sala Especial del Tribunal Suprem, a instàncies de les demandes de l’Advocacia de l’Estat espanyol i del Ministeri Fiscal, denegava la inscripció de Sortu en el Registre de Partits, en considerar que era una organització hereva de Batasuna i subordinada a ETA, però, a diferència de les anteriors, no fou una decisió unànime. Després de la negativa judicial, hom creà Euskal Herria Bildu, conjuntament amb tres formacions més del mateix signe: Eusko Alkartasuna, Alternatiba i Aralar, que malgrat diversos entrebancs judicials pogué participar en les eleccions del maig del 2011.
Al juny del 2012 el Tribunal Constitucional avalà el recurs contra la sentència del Tribunal Suprem i Sortu pogué ser legalitzat. Al febrer del 2013 celebrà a Pamplona el congrés constituent, en el qual aprovà les bases del partit, centrades en la sobirania d’Euskal Herria i en la recerca de la pau. S’hi elegiren també els principals líders, entre els quals el parlamentari alabès de Bildu i antic dirigent de Batasuna Hasier Arraiz, com a president. Per al càrrec de secretari general fou elegit Arnaldo Otegi, aleshores empresonat, i que no fou alliberat fins al març del 2016. En el congres de refundació d'EH Bildu (juny del 2017) Otegi fou elegit coordinador general i hom acordà integrar les quatre formacions en un sol partit.