Having moved to Belgium at the age of sixteen,[2] he became a naturalised citizen of Belgium in November 2008.[3] His first international appearance for his adopted country came at the 2008 European Cross Country Championships. He ran in the under-23 section of the competition, but failed to finish the race.[2]
In 2010 he competed on the global stage for the first time. Running as a senior, he was Belgium's only entrant at the 2010 IAAF World Cross Country Championships and he was 94th overall.[7] He also represented Belgium at the European Cup 10000m, placing 14th in his race. In the winter cross country season, he reached the podium at the Warandeloop and CrossCup Mol races. He suffered an injury prior to the 2010 European Cross Country Championships, where he went on to finish 54th.[5]
A significant personal best of 13:43.20 minutes over 5000 meters in Nijmegen in May 2011 marked the beginning of an improvement in Atelaw's running.[8] After high-altitude training in Ethiopia, he returned to Europe and won the Lotto CrossCup Roeselare race.[9] At the 2011 European Cross Country Championships he seized the lead after 2 km by increasing the pace and was never challenged thereafter, taking the gold medal five seconds ahead of runner-up Ayad Lamdassem.[10] He was the top European behind Kenya's Isiah Koech at the Lotto Cross Cup Brussels meet later that month.[11]