Under sommaren 2002 var Cissé lagkapten för Senegal som tog sig till kvartsfinal i fotbolls-VM efter att ha slagit ut bl.a. Frankrike. Efter imponerande spel för landslaget drog Cissé till sig intresset från engelska klubbar och flyttade till Birmingham City FC inför säsongen 2002/2003.
Han gjorde debut mot Arsenal i första matchen för säsongen men blev utvisad. Trots att utvisningen återkallades fortsatte hans aggressiva spel och fick fem gula kort på sex matcher och sammanlagt tio gula kort före årsskiftet.
Trots hans brist på disciplin imponerade han på klubben tills han åsamkades en skada i februari 2003 som gjorde att han inte kunde spela för resten av säsongen. Han blev sedan försenad till försäsongsträningen i juli 2003 vilket ledde till att tränaren Steve Bruce satte honom på transferlistan.
Cissé kom tillbaka till startelvan men hans förhållande till Bruce fortsatte att gå utför och efter julen spelade han bara tre matcher för resten av säsongen. I slutet av säsongen skrev han på ett tvåårskontrakt värt 300 000 brittiska pund för Portsmouth.
2002 förlorade Cissé tolv släktingar i Le Joola-olyckan som sammanlagt kostade minst 1 863 liv när den kapsejade på Gambias kust.[1]