Tout Puissant Mazembe was founded in 1939 by Benedictine monks of the order of Sanctimonious Saint that directed the Holy Institute Boniface of Élisabethville (Lubumbashi). To diversify the student activities for those that did not consecrate themselves to the priesthood, the missionaries decided to set up a football team, named Saint Georges FC, after the patron of the Troop. This team affiliated itself directly in the first division of the Royal Federation of the Native Athletic Associations (FRASI for FrenchFédération Royale des Associations Sportives Indigènes) founded by the Belgian King. At the end of the season, Holy Georges placed 3rd.
In 1944 the young scouts went on the road and FC St. Georges was rechristened Saint Paul F.C. Some years later, the incorporation of certain foreign elements in the Institute would make the missionaries abandon the team management. The team took the name of F.C. Englebert after its sponsor, a tire brand. The qualifier "Tout Puissant" (Almighty) was added to the club's name after it went undefeated in winning its first league title in 1966.
In 1967 and 1968, it won the African Cup of Champions. The team would be finalist four times successively in (1967,1968.1969 and 1970). Mazembe was the first team to successfully defend the African Champions Cup. This feat was finally repeated in 2003 and 2004 by Enyimba.
After 18 years of absence, it returned to the African scene thanks to 38 year-old governor Moïse Katumbi Chapwe.
By winning the CAF Champions League, they qualified for the 2009 FIFA Club World Cup. In their first match in the quarter-finals they lost 2-1 to Pohang Steelers of South Korea. despite taking the lead in the first half. Following a 3-2 defeat to Auckland City FC in the fifth placed match they finished the tournament in 6th place.