In 2001, Raj Binder Singh became the first Kenyan of Asian origin to become chairman of a major football team when he became chairman of Gor Mahia. He became the third club chairman in two years. His main brief was to secure sponsorship for the club. The sponsorship never came to fruition. Not sure why anyone thought that he would be able to secure sponsorship
The year 2002 will go down in history as the worst in the history of the club. They finished with a record of 3 wins, 4 draws , 12 losses and a goal difference of minus 20 goals. Only Re-Union had a worse record. For the first time in the club's history, Gor Mahia was relegated from the top flight.
The club had finally sunk to depths which would have been unthinkable only 5 years earlier. The league had been divided into two groups. Gor Mahia finished at the bottom of group B behind other relegated teams like Pan Paper and Mombasa Heroes. They however received a reprieve from the Kenya Football Federation (K.F.F). Even after the reprieve, the club officials could not get their act together and save the club from further ignominy.
In 2003 Gor Mahia was the runner-up in the K.P.L Transparency Cup Championship and received a cash award of Ksh 500,000, the largest amount ever received in the 35-year history of the club. Gor Mahia player Kenneth Omondi received a cash award of Ksh 10,000 for the Best Player with team mate also receiving the same amount for Best Fair-play.
In 2004 at the end of the 2003-04 season, Gor Mahia had won only two games and finished in last place but avoided relegation when the K.F.F and Premier League clubs agreed to reconcile and form a "unified league" with 24 clubs playing in two groups with the last three clubs in each group to be relegated at the end of the 2004-05 season.
In 2005 at the end of the 2004-05 season, Gor Mahia had won only six matches and ended among the three last clubs to be relegated in Group A and were relegated.
However in August the same year Nzoia FC dropped out of the league. Gor Mahia and Securicor were scheduled for play off matches to decide which team would replace Nzoia in the league but K'ogalo did not honour the fixture granting their opponents a lee way back to the league. But barely a month after in September, Kenya Pipeline too dropped out of the league and was replaced by Gor Mahia.
In 2007 K.F.F decided to set up their own league, K.F.F PL, in an effort to dismantle the KPL. Gor Mahia and relegated teams Shabana, Kangemi and AFC Leopards were added to bring the league tally to twenty teams. FIFA intervened to unify KFF-PL and KPL.
Whereas KPL wanted Gor Mahia relegated, Jerome Champagne insisted that Gor Mahia remain in the league. The season ended with Gor Mahia finishing eleventh out of sixteen teams.
2008 heralded a new era for the club when Ambrose Rachier was elected Chairman. The years between 2001 and 2008 had been by far the worst for the club. The entry of a new set of officials was indeed seen as a breath of fresh air by fans who desperately wanted a forward thinking chairman with ideas of how to restore the club's past glory.
In the same years, Gor Mahia won the Presidents cup after beating Posta Rangers 2-0 in the final, thus earning the right to play continental football for the first time in about a decade.
So in 2009, Gor Mahia sought fresh start. Coach James Siang'a went about recruiting young players to build a team for the future. In came players like Ibrahim Kitawi, George Odhiambo, Duncan Owiti, Chris Wekesa amongst others.
Kogalo played APR of Rwanda in the first round of the CAF cup. The young players some of whom were still in secondary school were clearly over awed by the occasion. Their stage fright and inexperience showed as they lost by five goals. Gor Mahia however went on to play a stormer of a second leg in the KPL that saw them leap from tenth position to finish fifth in the league.
George Odhiambo now dubbed "Blackberry" was voted young player of the year by a panel of journalists and along with Peter Opiyo, Julius Owino and Ibrahim Kitawi, was named to the national team.
In 2010 Kogalo started the season with two coaches; Gideon Ochieng 'Agido' was the head coach and former full back Zedekiah Otieno was designated as the Technical Advisor. That arrangement did not last long as it reportedly caused divisions in the camp and most players sided with Ochieng.
As the clubs top brass wanted Zico- a club legend, and Ochieng was sidelined in midway through the season. Gor Mahia went on to play strongly in the second leg of the league and came within a whisker of winning the league. The league winner was determined on the last day of the league and Gor Mahia finished second behind Ulinzi Stars.
At the end of the year, George Odhiambo 'Blackberry' , who had played two stellar seasons for Gor Mahia and finished second in KPL scoring, secured a four year contract with Danish top tier side, Randers FC. Odhiambo was also voted KPL player of the year.
From a financial perspective, 2011 was a landmark year because that was the year that Gor Mahia secured a shirt sponsorship for the first time ever. Previously in 1991, Gor Mahia wore shirts emblazoned "International Casino". However the proceeds from that sponsorship then were unknown and clouded in mystery. The Tuzo sponsorship was the most lucrative by any club in Kenya.
Also in 2011, Gor Mahia won the local cup, now called the F.K.F Cup after beating Sofapaka 1-0 in the final thanks to a goal by Edwin Lavatsa. Gor Mahia thus qualified for the CAF Confederations cup.
The beginning of 2012 was a tumultuous time for Gor Mahia. In a bid to strengthen the team, the club went on a signing spree. Seven players were recruited; George Midenyo, Hugo Nzoka, Ivo Mapunda, Yusuf Juma, Rama Salim, Felixinho Nwosu and Antony Otieno
Gor Mahia started the season disastrously, losing 4-0 aggregate in the opening round of the CAF cup to Ferroviario of Mozambique. They also played poorly in the league. By the time the league was six games old, Gor Mahia were in the relegation zone. It turned out that much of the poor performance was due to infighting within the bloated technical bench and the Executive committee. In a bid to stem the tide of poor performance, the club sacked the entire technical bench including Coach Anaba Awono, former captain Julius Owino, team manager Ouma Ole Tunda and assistant coach Ken Odhiambo.
Legendary stopper Bobby Ogolla took over as coach on a interim basis, assisted by Tom Ogweno. Two weeks later, Croatian Coach Zdvarko Logarusic was appointed as coach.
Logarusic soon overhauled the team getting rid of almost a dozen players including Demonde Selenga, Hugo Nzoka and later Dan Makori and Ibrahim Kitawi. The arrival of Logarusic caused a change in fortunes for the team. Gor Mahia went through a stretch of a dozen games where they did not loose. By September, Gor Mahia were amongst the league leaders. By the last match of the year, Gor Mahia were leading with only a game left. They needed to beat Thika United in the last game to clinch the league. However they were held to 1-1 draw and ended up finishing second to Tusker.
Having narrowly lost the league in 2012, Gor Mahia started the league in determined fashion in 2013. And with coach Logarusic enforcing discipline and professionalism both on the field and amongst officials, Gor Mahia for the first time in many years started the season with stability.
It was not without drama however; Gor Mahia announced with much fanfare that they were signing a Brazilian by the name of Giovanni Rodriguez Bissolli. However when the Brazilian arrived he was out of shape and clearly out of his depth. He was soon shown the exit by Logarusic who claimed that the Brazilian was lonely. Still Gor Mahia started the league well and by mid-season , they were leading the league thanks largely to a solid defence in which goalkeeper Fredrick Onyango stood tall along with David Owino, Donald Mosoti, Musa Mohamed and Ugandan Israel Emuge.
However drama ensued as Logarusic declined to return from his vacation during the halfway break of the league. He was fired and promptly replaced by former Uganda Cranes coach Bobby Williamson. Gor Mahia suffered another blow when influential attacking midfielder, Rama Salim who had been Gor Mahia's second leading scorer for the past two years left for Al-Markhya of Qatar.
Nevertheless, Williamson soon brought stability. Ugandan Striker Danni Sserunkuma went on a tear during the last stages of the league, scoring in virtually every game. Gor Mahia held on to their league despite a determined chase by arch rivals AFC Leopards and went on to win the league for the first time in 18 years.