With Haile Gebrselassie as his training partner, he continued to improve, winning the junior race and taking bronze in the senior short course for a medalling double at the 1999 World Cross Country Championships.

Mekkonen attended the 1999 and 2001 World Championships in Athletics and represented Ethiopia at the 2000 Summer Olympics, but he failed to make the podium at any of the events.

Mekonnen came to prominence at the age of eighteen with a silver medal performance in the 5000 m at the 1998 African Championships in Athletics, finishing behind reigning world champion Daniel Komen.

[3] However, Mekonnen only managed sixth place in the short race at the 2000 IAAF World Cross Country Championships, but again he won the team bronze with Ethiopia.

Competing at his first IAAF World Indoor Championships, he finished seventh in the final of the 1500 m. After this he decided that he would not succeed over distance and permanently switched to the 5000 m, saying: "That’s enough for the 1500.

He had his best ever cross country result at the 2002 edition in Belfast, winning a bronze medal for himself and helping Ethiopia to the team silver in the short race.

[6] At the 2003 All-Africa Games, he decided not to defend his 1500 m title and instead opted for the 5000 m and he won the silver medal, just beaten by Kenenisa Bekele.