A védőként is bevethető, szenegáli származású, francia U20-as válogatott játékos 2012 júliusában 1.3 millió euróért cserébe érkezett a Metztől a Genkhez, amellyel négyéves szerződést írt alá.
„A tárgyalások jól haladnak – mondta a 195 centi magas játékos ügynöke, David Wantier. – Még van hátra pár dolog, hogy véglegesítsük a műveletet, de előrehaladott tárgyalások zajlanak a csapatok között. Jelenleg várjuk, hogyan alakul a helyzet.”
„A Napoli nagy csapat, és természetes, hogy ott akar játszani – mondta Koulibalyról az ügynöke. – Az esélyek nagyon jók, de először bizonyos kérdéseket még meg kell oldanunk. Rafa Benítez már egy ideje figyelemmel követi őt. Megtiszteltetés lenne Koulibalynak egy ilyen szintű edző kezei alatt játszania.”