The first decade of new millennium were mostly years of pain and anguish for AFC fans. Constant infighting and poor organization amongst club officials assured that the club hit rock bottom. By around 2005, the club had been relegated to to lower divisions, only to be saved by backroom deals. Finally in 2006, the club was indeed relegated and found itself playing in the Kenyan second tier. Whereas in the 1980s, AFC played to large crowds in large stadia all over Africa, whereas in the 1980s, the name AFC sent shivers down the spines of opponents all over Africa, the club was now playing in run down fields with no terraces against no name teams. And they were still struggling.

 

In 2007, AFC were to miss out on promotion when they finished behind Eldoret Mahakama in the nationwide league. However Mahakama were disqualified and this paved the way for AFC to return to the Kenya Premier league. AFC were thus promoted back to the Kenya premier league. The timing was good since the league was going through a revival in fortunes thanks to better organization.

When AFC returned to the Kenya premier league in 2008, they were received emotionally by their long suffering fans who were simply happy to see the team back in the top tier. AFC matches were well attended with scenes nad passion sometimes matching that seen in the 1980s. AFC strengthened their team by signing new players such as the exciting Congolese duo of Itubu Imbem and Demonde Selenga.