Stéphane Badji begon zijn carrière in de voetbalacademie Ècole de football Mamadou Fayé.[1] Samen met zijn broer, Ismaïla Diarra Badji, maakte hij in de loop van het seizoen 2007/08 de overstap naar ASC Xam-Xam, een club uit de hoogste divisie. In de zomer van 2009 maakte de middenvelder de overstap naar reeksgenoot Casa Sports. In 2011 veroverde hij met zijn ploeggenoten de Senegalese beker. In het seizoen 2011/12 was hij met Casa Sports op weg naar de eerste landstitel uit de clubgeschiedenis, maar besloot hij om halfweg het seizoen naar Europa te verhuizen.
Op 31 december 2011 versierde hij een transfer naar het Noorse Sogndal. Badji groeide in het jaar 2012 meteen uit tot een vaste waarde en werd een jaar later door reeksgenoot SK Brann aangetrokken. Hij tekende een vierjarig contract bij de Noorse club[2], maar zocht reeds in februari 2015 andere oorden op. De Senegalese middenvelder tekende bij het Turkse Istanbul Başakşehir.
Op 1 februari 2016 tekende Badji bij RSC Anderlecht. De Brusselse club betaalde zo'n 2 miljoen euro voor zijn komst.