In 2008, at the age of 18, Tembo moved from Zambia to Sousse in Tunisia and signed with the traditional club Étoile Sportive du Sahel, who played in the Tunisian Ligue Professionnelle 1.
On 29 May 2010, The Newspaper Post (Zambia) announced online that Tembo had joined FC Basel from Étoile Sportive du Sahel on a three-year deal, for a reported fee of €1.2 million.
[5] He scored his first league goal for his new club on 14 August in the home game in the St. Jakob-Park as Basel were defeated 1–4 by FC Luzern.
[7] He scored another goal from the penalty spot on 10 April 2011 in the away 3–3 draw against BSC Young Boys in the Stade de Suisse.
[9] Although mainly used as joker, Tembo won the Swiss Championship with Basel at the end of the 2010–11 season, topping the table just one point clear of rivals Zürich.
[10] To the beginning of their 2011–12 season Tembo was member of the Basel team that won the 2011 Uhrencup, beating both Hertha Berlin 3–0 and West Ham United 2–1 to lead the table on goal difference above Young Boys.
But Tembo returned to Sousse in Tunisia and rejoined Étoile Sportive du Sahel on a loan deal.