Deze tweede stad van Georgie is een van de oudste ter wereld. Het was een van de belangrijkste steden in Colchis en een nederzetting bestond hier al bijna 4000 jaar geleden. In de derde eeuw v Chr refereerde Apollonius van Rhodos aan Kutaia in een gedicht over de Argonauten. Sommige geleerden geloven dat dit de stad was van koning Aeetes, de vader van Medea.

Aan het einde van de achtste eeuw verzaakte Leon II aan de Byzantijnse suzereiniteit en verklaarde zichzelf koning van Abkhazie. Hij verhuisde zijn hoofdstad van Anakopia (in het hedendaagse Abkahazie) naar Kutaisi. In 1001 erfde de Abkhazische koning Bagrat III het Oost-Georgische koninkrijk Kartli waardoor hij oost- en west-Georgie voor het eerst in vele eeuwen verenigde. Het was in Kutaisi dat David de Bouwer gekroond werd in 1089. Deze twee koningen lieten grootse monumenten achter in de vorm van de Bagrati en de Gelati kathedralen.

Kutaisi was het politiek, economisch en cultureel centrum van Georgie tot 1122, toen David Tbilisi bevrijdde van de Arabische heerschappij. Kutaisi hernam zijn rol als hoofdstad van West-Georgie toen het koninkrijk opgesplitst werd in de 15de eeuw na de invasies van de Mongolen en Timur. In de vroege 17de eeuw ontwikkelde Giorgi III van Imereti de linkeroever van de Rioni maar de stad leed vanaf 1669 onder een 101-jarige Ottomaanse bezetting. Tijdens die bezetting werd de Bagratikathedraal opgeblazen. In 1770 werd de stad heroverd door Georgische en Russische krijgsmachten. Onder het sovjetregime werd Kutaisi het tweede belangrijkste industrieel centrum van Georgie en de bevolking groeide snel aan, om dan weer af te nemen na het afnemen van de industrie na de Georgische onafhankelijkheid. Georgie is gebouwd rond de Rionirivier. Het stadscentrum bevindt zich op de linkeroever, rond het David Aghmasheneblis plein en het aanliggende centrale park. De moderne stad strekt zich uit naar het zuiden en westen.