Hljómsveitin var stofnuð árið 1991 af þeim bræðrunum DJ Paul og Lord Infamous, hljómsveitin gaf fyrstu plötuna sína Mystic Stylez árið 1995, svo árið 1997 fengu þeir samning við Relativity Records og gáfu út sína fyrstu stóru plötu Chapter 2World Domination sem innhélt t.d. lagið Tear Da Club Up. Árið 2003 gáfu þeir svo út plötuna Da Unbreakables og á þeirri plötu heyrist í en bara mafia heldur t.d líka Lil Flip, Pimp C þessi plata innhélt hið vinsæla lag Ridin Spinnaz sem featuraði lil flip.
Árið 2005 gáfu þeir svo út plötuna Most Known Unknown, en Lord Infamous tók ekki þátt í þessari plötu, mafia sögðu að infamous væri í fríi en nýlega hefur hann komið aftur, platan þessi innhélt hit lagið Stay Fly.
Í mars 2006 urðu þeir fyrsta african-american hip-hop hljómsveitin til að vinna academy verðlaun, lagið sem var tilnefnt var It's Hard Out Here for a Pimp, einnig eru þér frægir fyrir að hafa spilað lagið Some Bodies Gonna Get It í Smakdown, þann 26. maí 2006 í boði WWE kappans Mark Henry og er lagið núna lagið hans í WWE.
Shh My Common Sense is Tingling