The club was founded on 12 April 1963 by Samuel Wamala, who was head of the Council’s Sewage Works section in the City Engineering Department. The club initially was dominated by casual workers in the sewage section but subsequently expanded to cover all departments within Kampala City Council.^[3][4]

In 1965 KCC joined the Kampala and District Football League (KDFL) Third Division (which was split into two sections) and under the guidance of Bidandi Ssali (Head Coach) and Samuel Wamala (Chairman) the club soon progressed. After finishing in sixth place in their first season, in 1966 they gained promotion from the Third Division South after finishing in second place.^[3][4]

By 1968 KCC were playing teams like Express FC, Army FC, KDS (Kampala District Bus Services), Railways, UEB and Nsambya in Division One of the KDFL but in 1971 they were relegated back to the Second Division. By this time the KDFL was being run concurrently with the National Football League and subsequently was scrapped to allow room to a wider national competition with several divisions. KCC became a member of the newly formed second division of the National League along with Nsambya and NIC.^[3][4]<that was the lead>

By 1974 KCC had gained promotion to the National League and finished in second position in both their first and second seasons in the top tier just one point behind champions Express FC on each occasion. The following season in 1976 KCC won their first championship title finishing one point ahead of Express. They also won the title in 1977 in a more emphatic manner although during this season Express were banned for allegedly being involving in anti-government activities.^[3][4]

Simba FC (the Army side) finished as champions in 1978 with KCC taking second place but the Council side won the CECAFA Clubs Cup, the regional club championships in Kampala, becoming the first Ugandan side to take the regional title. The trophy was presented to the KCC skipper, Sam Musenze, by President Idi Amin. Players representing KCC included Phillip Omondi, Jimmy Kirunda, Jamil Kasirye, Hussein Matovu, Tom Lwanga, Sam Musenze, Yusuf Toyota, Peter Mazinga, Apolo Lumu, Billy Kizito, Hussein Matovu, Chris Dungu, Gerald Kabaireho, Ashe Muksa, Rashid Mudin, Moses Sentamu, Timothy Ayeieko, Angelo Dotte and Hassan Biruma, Peter Wandyette.^[3][4]

The 1978 team broke up with some senior players turning semi-professional and moving to the United Arab Emirates. However, following the recruitment of youthful players such as Godfrey Kateregga, Sam Mugambe and top-scorer Davis Kamoga the club made an impact on the Ugandan Cup winning the competition in 1979 having been awarded a walkover for their match against Uganda Commercial Bank FC in the final.^[3][4]

The club enjoyed their halcyon days in the 1980s by winning the Uganda Cup in 1980, 1982, 1984 and 1987 and the league championship in the intervening years in 1981, 1983 and 1985. The goal scoring exploits of Davis Kamoga, with 21 goals in 1980, and Frank Kyazze, with 18 goals in 1984 and 28 goals in 1985, made a major contribution to the club’s success.^[5]

A less successful period followed although KCC did take the Super League title in 1991 and 1997 and the Uganda Cup in 1990 and 1993. After the 1997 championship success there followed a period of administrative problems and upheaval including the appointment and sacking of a succession of coaches .

In 2007–08 KCC won the league championship for the first time in over a decade with a rising star in striker Brian Umony who netted 15 goals and subsequently moved on to professional ranks with Supersport United of South Africa. In 2012–13 the club repeated the feat by finishing 7 points ahead of Uganda Revenue Authority SC. The other success in the last decade was a Uganda Cup title in 2004 2017 and 2018

On the international club football front KCC reached the quarter-finals of the African Cup of Champions Clubs in 1978 and 1982 and made second round appearances in 1977, 1984, 1986 and 1992.^[6] In addition they have made three appearances in the CAF Champions League in 1998, 2009 and 2018; four appearances in the CAF Cup in 1995, 1997, 2001 and 2002; three appearances in the CAF Confederation Cup in 2005, 2009 and 2017; and finally seven appearances in the CAF Cup Winners’ Cup in 1980, 1981, 1983, 1985, 1988, 1991 and 1994.^[7]

In total KCC (now known as KCCA FC) have won 13 Uganda league championship titles, the last one being in 2019 and 10 Ugandan Cup titles, along with 2 CECAFA Clubs Cup in 1978 and 2019 wins at the regional level.