Bedi Mbenza begon zijn spelerscarrière bij AC Dynamique. In 2006 belandde hij in de Congolese hoofdstad bij Bel'Or FC, waar hij na twee seizoenen al werd opgemerkt door de topclub TP Mazembe. De aanvallende middenvelder veroverde met Mazembe twee keer de landstitel en twee keer de CAF Champions League. In 2010 bereikten de Congolese international en zijn ploegmaats ook de finale van het WK voor clubs.
In het seizoen 2011/12 trok TP Mazembe op stage in Anderlecht. Mbenza en zijn ploegmaat Patou Kabangu maakten indruk en tekende niet veel later een contract bij RSC Anderlecht. De twee werden bij paars-wit verenigd met hun landgenoot Dieumerci Mbokani, eveneens een ex-speler van Bel'Or en Mazembe.
In 2013 ging hij in Tunesië voor Club Africain spelen. Hij keerde terug bij TP Mazembe en speelde in 2015 in Angola voor Kabuscorp SC. In 2016 ging hij voor FC Renaissance spelen.