Andamlak Belihu trat erstmals 2017 bei den nationalen Meisterschaften an. Dabei konnte er auf Anhieb en Titel über 10.000 Meter in 28:32 min gewinnen. Nur einen Monat später verbesserte er seine Zeit um mehr als eine Minute und ging im August dann auch bei den Weltmeisterschaften in London an den Start. Dabei lief er noch einmal mehr als zehn Sekunden schneller als seine Zeit aus dem Juni und landete im Ziel mit einer Zeit von 27:08,94 min auf dem zehnten Platz. Im November nahm er an seinem ersten internationalen Rennen im Halbmarathon teil. Dabei blieb er in Neu-Delhi unterhalb einer Laufzeit von einer Stunde und kam als Zweiter ins Ziel. Im Laufe des Jahres 2018 nahm er in einer Vielzahl von Halbmarathons, verteilt auf Europa und Asien, teil. Seine beste Zeit lief er erneut in Neu-Delhi. Gut zwei Monate zuvor trat er über 10.000 Meter bei den Afrikameisterschaften in Nigeria an. Dabei lief er eine Zeit von 29:11,09 min und sicherte als damit als Zweiter hinter Jemal Yimer den Äthiopiern den Doppelsieg.
Im Frühjahr 2019 trat Belihu bei den Crosslauf-Weltmeisterschaften im dänischen Aarhus an. Dabei startete er im Erwachsenenrennen über 10 Kilometer und belegte mit einer Zeit von 32:29 min den achten Platz. Im Juli verbesserte er seine Zeit in Hengelo über die 10.000 Meter auf 26:53,15 min. Beinahe gelang es ihm im Oktober bei den Weltmeisterschaften in Doha diese Zeit zu bestätigen. Dort blieb er rund drei Sekunden hinter seiner Bestzeit zurück und erreichte insgesamt als Fünfter das Ziel. Im Oktober trat er erneut im Halbmarathon von Neu-Delhi an. Mit seiner Zeit von 59:10 min, die er dabei lief, rückte er, Stand November 2020, auf Platz 43 der ewigen Weltbestenliste über diese Distanz vor.[1] Zudem näherte er sich bis auf vier Sekunden dem Streckenrekord in der indischen Hauptstadt an.[2] Im Oktober belegte er bei den Halbmarathon-Weltmeisterschaften in Saisonbestleistung von 59:32 min den fünften Platz. In der Teamwertung gewann er, zusammen mit seinen Landsleuten, die Silbermedaille.
Im September 2022 erzielte Belihu als Viertplatzierter beim Berlin-Marathon mit 2:06:40 Stunden eine neue persönliche Bestzeit.