Koutialát a 16. században alapították a bambara királyságbeli [[Ségou]]ból jött Coulibaly nevű uralkodócsalád tajai. Ekkor a város a minianka nép államához tartozott. Idővel azonban megjelentek a francia gyarmatosítók és Koutiala a mai Mali területén létrejött [[Francia-Szudán]] gyarmathoz került. A város csupán 1955-re kapott az európai városokéhoz hasonló jogot, vagyis önkormányzatát saját maga szervezhette meg. Ekkor alapították a város főiskoláját is.<ref>[http://www.legifrance.gouv.fr/affichTexte.do;jsessionid=C35E6F788FA13346576E6AD6C6FEC07D.tpdjo02v_2?cidTexte=JORFTEXT000000313008&dateTexte=19551119&categorieLien=cid] Politikai változások Észak-Afrikában (francia nyelven)</ref> Ám 11 évvel később, Mali függetlenné válása után újra változott a közigazgatás, és azóta az 1966-os törvény alapján a városi tanácsnak kell megválasztania a polgármestert, illetve annak helyetteseit.<ref>http://penserpouragir.org/espace-de-reflexion/reseau-reussir-la-decentralisation,22/recherche-sur-l-historique-de-la.html</ref>
