Teklehaimanot est nommé à la tête de l'équipe nationale en janvier 2008, à la suite du court passage de Tsegaye Desta (moins de six mois). Son mandat débute de bien sombre façon puisque le [2], les manquements de la fédération éthiopienne vis-à-vis de la FIFA entraînent la suspension de toute compétition officielle. Par conséquent, les Walya, engagés dans les éliminatoires de la Coupe du monde 2010, en sont exclus alors qu'il ne reste que deux rencontres à jouer lors du premier tour. Les éliminatoires étant communes pour la Coupe du monde 2010 et pour la CAN 2010, l'Éthiopie perd également toute chance de disputer le tournoi continental, prévu en Angola. De la même façon, il lui est impossible de prendre part à la Coupe CECAFA des nations 2009.
La suspension est levée un an plus tard, en juillet 2009, à la suite de l'élection d'un nouveau collège dirigeant au sein de la fédération. Teklehaimanot peut donc reprendre son poste pour préparer la Coupe CECAFA des nations 2009. Le résultat est décevant avec une élimination à l'issue de la phase de poules, l'Éthiopie se classant troisième derrière la Zambie et le Kenya.
Le technicien éthiopien est démis de ses fonctions en juin 2010. Il est remplacé par le Nigérian Ifem Onuora. Avec une durée de deux ans et demi, son mandat reste le plus long effectué par un entraîneur à la tête de la sélection éthiopienne.
