The conflict between Ethiopia and Eritrea has brought a major setback to the peace and security of the two countries with devastating impacts against the wider Horn of Africa. Efforts made to bring the warring parties to a lasting solution have continued to fail. The conflict is more deeply rooted and complex than a simple territorial issue. In the process, the mediator's efforts including the Algiers agreement have failed to resolve the crisis because of lack of proper understanding of the root causes of the conflict. This has led both countries to remain in 'no war and no peace' situation, with the potential for destabilizing each other. As is often said, 'knowing the problem is half way to the solution', the key to the whole effort in resolving the Ethiopia-Eritrea conflict is to be found in deeper analysis of why the previous efforts had fai led and thoughtful inquiry of critical factors that lie beyond the superficial causes of the conflict. Having a clear understanding of the root cause of the conflict is very important to make an assessment of the attempts made so far have helped to end the hostility or they have just perpetuated it. To this effect, this study identified political and historical factors as a subsidiary causes while territorial disagreement has been a pretext. It argued that the economic issues and the conception of military invincibility were comparatively the cardinal causes of the conflict. Finally, the research concludes that the way out from the current deadlock depends on the legal and political options. But both these options did not have common ground and lack the critical element of a win-win approach that can reconcile both parties' respective national interests. Even though the issue still remains largely as a legal case, its final and sustainable solution depends on comprehensive political dialogue and concerns. Therefore, the thesis finally proposed the need to undel1ake a series of mutual interest based negotiations and the initiative along with committed political dialogue and demarcation as a creative approach to end the current stalemate .