Conflicting views of the Eritrean independence war as a solitary, single-handed struggle against the Ethiopian Empire on the one hand and assertions about Eritrean diplomatic ineptitude on the other abound in the discourse on Northeast Africa. Both positions defy the age-old adage that war and diplomacy are enduring features of human interaction, and overlook African experiences with liberation diplomacy. This article revisits Eritrean nationalists’ hydra-like diplomatic dealings with an array of forces in the region and beyond to show that their diplomacy of liberation was indispensable to the heated battles (1961-1991), and that, as a result, they received materiel, political and humanitarian assistance without which their movement would have been hard pressed to succeed. They particularly forged political-military alliances with Ethiopian insurgents to clinch the all-important but elusive international recognition after military victory in Asmara and parallel regime change in Addis Ababa.