Tshombe föddes i en rik familj i Katangaprovinsen i Belgiska Kongo. Åren 1951–53 satt han i Katangas provinsråd. År 1959 blev han ordförande för Conakat, ett politiskt parti, som stöddes av lundafolket och belgiska gruvintressen.