In 1980 , Gor Mahia qualified to play in the CECAFA cup alongside arch rivals Abaluhya FC. David Otti was hired as coach. Otti had an illustrious playing career for Uganda Cranes whom he also coached when they qualified for the Africa Nations cup in 1976. In the CECAFA cup, Gor Mahia made it to the final where they faced Abaluhya in an all Kenyan final. Joe Masiga who had been flown in from Nairobi to reinforce Abaluhya scored the match opener. Gor Mahia replied via George Yoga following a pass from Nahashon Oluoch 'Lule' who had dribbled passed defender Washington Wabwire. Masiga scored again after beating his marker Duncan Migan to put Abaluhya up 2-1 soon after the 1st half. John Chore equalized for Gor Mahia following a cross from Paul Oduwo 'Cobra'. Nahashon Oluoch scored the winner to give Gor Mahia a 3-2 win as Gor Mahia lifted the CECAFA cup for the 1st time ever. George Ayuka the Gor Mahia goalkeeper was the man of the match, pulling off a series of brave saves. On the continental scene , they featured in the Africa champions cup. They almost did not play in the champions league due to attempted sabotage by Dan Owino the FA chairman who deliberately failed to send player cards to CAF headquarters. Only intervention from the ministry of social services assured participation. The round pittend Gor Mahia against Horseed of Somalia. The 1st leg in Mogadishu ended 0-0. Gor Mahia won the second league 2-0 thanks to goals from Goerge Yoga and Andrew Obunga.

After beating Horseed of Somalia in the first round, they lost to Bendel Insurance of Nigeria in the second round. Gor Mahia won the 1st leg 2-1 in Benin city thanks to goals from George Yoga and Austin Oduor. Another goal by Yoga was disallowed. According to the Nigerian press, Gor Mahia had totally outplayed the Nigerians. Gor Mahia looked poised to win the second leg in Nairobi or at least force a draw which would enable them to advance. The Nigerians took a 2-0 lead but Gor Mahia fought gamely to tie the score with goals from Mike Adede and Andrew Obunga aka "Obung Singh". They appeared on their way to the quarter finals but with 5 minutes to go Bendel scored from a 30 yard free-kick by Ibrahim Alikali who scored a heart trick. Bendel went on to to win the game 3-2 and advance to the quarter finals. Dan Odhiambo in the Gor Mahia goal had a poor game. For the Nigerians, winger Sam Okpodu was sensational as was George Omokaro. However Gor Mahia were the better side and should not have lost.

Andrew Obunga receiving the CECAFA CUP from Minister for Culture Jeremeiah Nyaga

In 1981 , Gor Mahia , fielding an array of new signings who included keeper Charles Ondiek and Dino Kitavi retained the East and central Africa club cup (CECAFA cup) when they beat Simba of Tanzania in the final played at the Nairobi city stadium. Nairobi mayor Nathan Kahara rewarded Gor Mahia by awarding them the city crest in appreciation for representing the city well. They finished second in the National league. Gor Mahia howver won the KFF challenge cup by beating Busia United thanks to goals by Abbey Nassur and Andrew Obunga. Earlier they had eliminated arch rivals AFC Leopards 1-0 thanks to a goal by Gideon Hamisi. On the continental scene, Gor Mahia played in the Cup winners cup. After receiving a walk over in the 1st round, they faced Horseed of Somalia in round 2. They won the 1st leg 3-0 in Nairobi with goals from Allan Thigo, Sammy Owino 'Kempes' and Nahashon Oluoch 'Lule'. They advanced after losing 0-1 in Mogadishu. In the quarter finals they faced Djoliba of Mali. After loosing the 1st leg 0-2, they won the second leg 1-0 with a goal from Abbey Nassur scored from the penalty spot after Nahashon Oluoch had been felled in the penalty area.

Zack Mbori was elected as the club's 3rs Chairman at the 1982 AGM. At the beginning of the year, players Andrew Obunga, Mike Ogolla 'Machine' Charles Ondiek and George Ayuka were serving suspensions for conduct unbecoming. Coach David Otti left for home after a 3 years stint. He was replaced by assistant Jerry Imbo. Peter Ouma 'Pele' became the assistant coach. At the beginning of the second leg of the national league, the team was involved in a road accident which resulted in serious injuries to players John Chore, Sammy Owino, George Otieno 'Vigo', Paul Oduwo 'Cobra', Mathew Onyango and Tim Ayieko. As a result, Gor Mahia were not involved in league matches for 2 months. On the continental scene, Gor Mahia were pitted against Dynamo de Fimia of Madagascar. They lost the 1st leg 2-3 with goals scored by Andrew Obunga and Gideon Hamisi. A disagreement between players and club officials led to Gor Mahia failing to travel to Madagascar for the second leg. Following the player rebellion, 6 players were suspended : George Ayuka, Charles Ondiek, Mike Ogolla 'Machine' Andrew Obunga, George Yoga and Nahashon Oluoch. In addition, the club was heavily fined by CAF.

Zack Mbori is congratulated by rival Luke Misiga whom he beat to the chairmanship

By the end of 1982 Nahashon Oluoch 'Lule' and Sammy Owino 'Kempes' , two players who were considered the best in the club had departed to the USA on football scholarships. Added to this , Playmaker Alan Thigo retired after an illustrious career that started when he joined the club in 1970. During his career he acted as coach, and captain on different occasions and is remembered by most fans in that era as possibly the best playmaker Kenya ever produced. Also retiring was tough tackling fullback Paul Oduwo 'Cobra' famous for always playing with a headband. Tim Ayieko who was now at the tail end of his career returned to Uganda. Following the departure of those stars , others like Sammy Onyango , Hamisi Shamba and Austin Oduor stepped to the forefront. Their shoes were however to large to fill. 1982 was a forgettable year for most fans. A year filled with turmoil, suspensions, key departures an unfortunate accident and continental campaign that ended in disarray. In 1983, Gor Mahia started the year off at the CECAFA cup which was held in Zanzibar. The team failed to make it beyond the 1st round. On the Continental scene they faced Vital O of Burundi in the 1st round. They won the first leg 2-1 in Bujumbura with goals from stopper John 'Bobby' Ogolla and Abdalla Shebe. However in the second leg, Gor Mahia inexplicably lost 3-0 at home. Irate fans protested and called for the return of former chairman David Opar. Following the match, George Ayuka, Charles Ondiek, Mike Ogolla 'Machine' and Andrew Obunga who were serving suspensions were expelled from the club after having been accused by club chairman Zack Mbori of inciting players to a poor performance. It also emerged that some club players had been bribed by officials of Ugandan side Sports club Villa during the CECAFA cup held in Zanzibar in January.

When the 1983 national league started, Gor Mahia had lost the 2 games and drew 1 game in the opening 3 matches of the league. Particularly painful was the 1-3 loss to kenya Breweries. It appeared the club was still suffering the effects of the disastrous year 1982. Fans demanded immediate changes. Patron Joab Omino and chairman Zack Mbori responded and brought in British coach Len Julians to replace Jerry Imbo. Long serving players like keeper Dan Odhiambo, Hamisi Shamba and John Chore stepped aside.

With the arrival of Julians, Gor Mahia recovered and were perched in the second spot of the league by the end of the 1st leg. The newly overhauled club was was now resurgent. Several youthful and new players who had been signed from relatively obscure provincial clubs made a big splash. Among them was goalkeeper David Ochieng "Kamoga" , probably the best goalkeeper ever to play for GorMahia, midfielders John Okello "Zangi", Peter Ochieng "Pierre" and Charles Otieno and strikers Hezborn Omollo and Abdallah Shebe. Under coach Julians the team played very attractive football and often left opponents bewildered with their brilliant interpassing play. The forwardline consisting of Shebe , Omollo , Hamisi and left winger Sammy Onyango was rampant scoring an incredible 80 goals in 36 league matches. That year the club won the league title , the first of 3 consecutive titles they won under Len Julians.

Captain Peter Otieno Bassanga holding aloft the league cup after receiving it from Minister Kenneth Matiba, perhaps the best, most proactive sports minister Kenya ever had

One of the biggest highlights of 83 came when Gor Mahia played a friendly match against British premier league side ,Norwich city. The Britons had expected to whitewash Gor Mahia as they did in an earlier tour in 76. This time it was Gor Mahia who silenced the visitors , winning 4-2. John Okello "Zangi" then only 18 played a superb game scoring twice while Gideon Hamisi and Hezborn Omollo completed the score. Another memorable moment for club fans occurred on October 20 when Gor Mahia faced arch rivals AFC Leopards in a Kenyatta day match. Gor Mahia required a win to guarantee the league title they had last won in 1979. On 32 minutes, winger Sammy Onyango waltzed passed full back Patrick Shilasi and unleashed a powerful grass cutter which qhizzed goalkeeper Mahmound Abass aka 'Kenya One' before he could react. Gor Mahia won the match 1-0 and at the end of the match, President Moi presented the league to captain Peter Otieno 'Bassanga'.