Cissé 1978. március 30-án született a Dél-Franciaországban található Pau városában, és a helyi csapatban ismerkedett meg a sportág alapjaival. Tizennyolc esztendősen már a felnőttek között szerepelt a harmadik vonalban, és olyan jól játszott, hogy egy évvel később a Paris Saint-Germain ajánlott neki szerződést.
Az első osztályban 1997. október 5-én mutatkozott be az FC Nantes elleni bajnokin, és a szezon során összesen 11 alkalommal vetették be. A következő idény erejéig kölcsönadták őt a szintén élvonalbeli Stade Rennes-nek, ahol rengeteg tapasztalatot szerzett, lévén a breton együttesben alapember volt, és 28 meccsen két gólt szerzett. Ekkoriban rendszeresen tagja volt a francia utánpótlás-válogatottnak is.
A PSG 1999 nyarán visszahívta őt, és azóta a fővárosi csapatban szerepelt. Eleinte még viszonylag sok lehetőséget kapott, és rendre ott volt a kezdő tizenegyben, az elmúlt idényben azonban többnyire már csak csere volt - igaz, még így is 25 összecsapáson szerepelt. Játékstílusát leginkább Patrick Vieiráéhoz szokták hasonlítani, rendkívül erőszakos futballista, aki sok labdát szerez a középpályán, és technikailag is jól képzett.