Coulibaly fu membro dell'Assemblea Nazionale dal 1995 al 1999 e fu anche consulente tecnico del primo ministro Alassane Ouattara. Nel 2001 venne eletto sindaco della città di Korhogo e l'anno successivo fu nominato dal primo ministro Pascal Affi N'Guessan come ministro dell'Agricoltura, rimanendo in carica fino al 2010.
Dopo l'elezione di Ouattara a presidente della Costa d'Avorio, Coulibaly diventò segretario generale della presidenza nel 2011. Rimarrà in carica fino al 10 gennaio 2017, quando fu nominato primo ministro.
Nel 2012 fu sottoposto a cardiochirurgia. Nel 2020 andò in Francia per sottoporsi a un esame del cuore, ma ritornò in Costa d'Avorio il 2 luglio di quell'anno. L'8 luglio Coulibaly subì un malore durante una riunione di governo e morì diverse ore dopo all'età di 61 anni.