Many of his finest races have been on British soil. Indeed, he won the Great Manchester 10km run in May as well as the 2011 Great Birmingham Run and 2010 Great North Run in Newcastle. He also chose London to be the place to make his marathon debut in 2002.
Just how much life is left in those legs, however, remains to be seen. According to his passport, the two-time Olympic 10,000m champion and former world marathon record holder will turn 40 on April 18. But there are many who, in the absence of accurate birth records in rural Ethiopia, believe he passed that milestone some time ago.
Gebrselassie admits he is in a transitional stage of his life. No longer is he solely a distance runner. A husband and father of four children, he has also assumed a place among Ethiopia's most prominent business leaders.
Nevertheless, he intends to run the 66th Fukuoka International Marathon on Sunday, December 2, a race he won in 2006. It will be his second visit to Japan this year. On February 26, he finished fourth in the Tokyo marathon in 2:08:17, just 27 seconds behind Stephen Kiprotich of Uganda who went on to win the marathon at the London Olympics.
The time is a far cry from the world record he set in Berlin 2:03:59 four years ago, but he is still competitive.
"I don't know exactly how fast I can run [in Fukuoka] but I can run a good time," Gebrselassie says. "I don't know, between 2:05 and 2:06, it depends. I mean, their course is so nice and it depends on the weather. For the moment I am in good shape and what is important is my health is very good. The only problem is that I have office work now. I cannot take rest after morning training sessions any more. My training is going well, though, and according to the programme."
Since winning the first of his four consecutive world 10,000m titles in Stuttgart in 1993, Gebrselassie has become a legend in the sports world and an icon in his homeland. Obligations have mounted accordingly and he has used the wealth he has acquired through running to play his part, with job creation a priority.
With his wife Alem sharing much of the day-to-day responsibilities, Haile & Alem International Plc has built schools, office complexes, cinemas and the five-star Haile Resort on Lake Awassa, 270km outside Addis Ababa. As if this wasn't enough, he also imports Hyundai cars into Ethiopia through his company, Marathon Motors. Future plans include building a Hyundai assembly plant in Addis.
"Now there is a really serious responsibility in Ethiopia because of the business I do," he says. "When you talk about business there's a human side, which means you have to take care of the humans and the business. I am responsible for 600 or maybe 700 people and you have to take care of them. I am trying. I am new to this type of job. It's different. I used to be a runner and now I am trying to change myself into a businessman. I can do it. The business is going well."
Gebrselassie has told foreign dignitaries that, despite their government handouts, there is still poverty in Ethiopia and it is better to invest in job creation. His own entrepreneurship has no limits.
"Now we have started farming a big coffee plantation," he says. "It's about 1500 hectares. It's a big one. We are hiring more people. Of course we have some bigger projects, the hotel, the school and when we make money from this one, we will build a bigger plantation.
"When somebody wants to help Ethiopia it's better to open something, a business can create jobs and then we have a winning situation: the country can win and the company can win."
With notoriety, of course, comes criticism and the runner has endured his fair share recently. When Ethiopian Prime Minister Meles Zenawi died in August at the age of 57, the image of Gebrselassie shedding a tear on national television infuriated some Ethiopians who were critical of Zenawi's human rights record. Gebrselassie prefers to look at the massive effect the late ruler had on the economy during his 20-year reign.
A year ago Zenawi opened the controversial Grand Ethiopian Renaissance Dam with Gebrselassie and other leading Ethiopian athletes in attendance. They had all contributed financially to the project.
"I don't understand why these people criticise," Gebrselassie says. "They are talking about democracy. If they accept democracy why do they criticise me? Why don't they accept it as my right? I accept their rights. They can complain about something, but do not criticise Haile Gebrselassie when he is trying to do his job and just because I was mourning for the prime minister. He was part of Ethiopia and it was a big loss for all of us, especially for athletics. Some people were talking about Ethiopia with problems. But what I know about this prime minister is he did a lot for sport and we started to recognise him after he passed away. He should have been recognised when he was alive. I am sorry for that because nobody expects they are going to die at such an early age."
Gebrselassie has been a United Nations Ambassador of Goodwill and a highly visible representative of his country. In July, he was delighted to be one of the eight world figures to carry the Olympic flag into the London Olympic stadium. He has talked about becoming a politician himself one day.
"That is what I was thinking," he admits. "I still don't know what I am going to do. We will see in the future. Right now I have to finalise the things I have started in athletics and business and then we will see."
In the meantime, the man who has refused to discuss retirement, saying that once you choose a retirement date you have already retired, will keep on running. The world records he held at 5000m and 10,000m now belong to his countryman Kenenisa Bekele. The marathon record is now 2:03:38 held by Kenya's Patrick Makau. Asked if he believes he is the greatest distance runner of all time, he shrugs.
"I leave this question for you and others," he says with the diplomacy of a politician. "I think people have their own measurement. For example, some people like Lionel Messi, others like Cristiano Ronaldo. Right now I have to do what I have to do. It's a difficult question to answer."