Kutai (Kutei) és el nom tradicional històric de la província de Kalimantan Oriental a l'illa de Borneo (Kalimantan), Indonèsia. El nom també és dona a un poble dayak de la regió i a un sultanat històric. Avui dia la província de Kalimantan Oriental està dividida en tres regències que porten el nom de Kutai: Kutai Kartanegara, Kutai Occidental o de l'Oest, i Kutai Oriental de l'Est. El principal riu de la regió és el Mahakam.
El sultanat de Kutai tenia una superfície de 45.190 km² i era equivalent a la regència de Kutai Kartanegara (Kutai Karta Negara). La religió de l'estat era l'hinduisme i fou un dels primers estats del sud-est asiàtic; la yupa (pal de sacrifici) més antiga es va trobar a les muntanyes Muara Kaman, o està datada vers el 400; les inscripcions votives esmenten al maharajah Mula Varman i al seu fill Acwa Varman. El seu desenvolupament fou independent dels regnes hindús de Java. Posteriorment no es tenen notícies de l'estat durant segles, fins que el 1365 apareix en un poema històric javanès, el Negarakartagama, on s'esmenta Kutai com a dependència de Majapahit. El 1420 va arribar l'islam al regne, per mitjà de comerciants musulmans. Segons la crònica de Kutai anomenada Salasila raja-raja di dalam negeri Kutai Kerta Negara l'islam es van introduir sota Raja Makota (1525 - 1600) el 1565, per obra de Tuan di Bandang (a les cròniques buguineses Dato'ri Bandang) però per poc temps. Després fou predicat per Tuan Tunggang Parangan a l'inici del segle xvii. Els dos predicador procedien de Makassar. El segon va utilitzar principalment procediments màgics descrits de manera viva a la crònica (redactada en temps del net de raja Makota, Aji Pangeran Adipati Sinum Panji Mendapa ing Martapura (1605 - 1635). Aquesta mentalitat animista i màgica ha restat en el fons del culte tradicional a Kutai; a la crònica queda clar que el adat, derivat dels costums tradicionals indígenes de culte, estava viu i vigent fins i tot a la cort del sultà de Kutai a Tenggarong.
Progressivament es van establir contactes amb el món exterior. El primer holandès que va arribar a la regió, el 1635, fou G. T. Pool, que hi va estar un temps no gaire llarg i després va marxar. Els mariners bugis van arribar el 1721, van derrotar el sobirà i van establir un colònia permanent a Samaranda agafant el control del principat de Pasir. Amb el temps hi va haver matrimonis entre dayaks i malais; els malais van restar com a població permanent servint com a soldats i policies. Sota influència dels bugis els islam es va desenvolupar. El 1726 o 1727 el príncep de Wajo, Aru Singkang, va conquerir per un temps Pasir i Kutai.
El rei de Kutai, restablerta la independència, segons es creu amb suport dels buguinesos (lleials tradicionalment al sultà, especialment en les guerres contra els dayaks del interior que eren pagans, i contra els pirates), va assolir el títol musulmà de sultà el 1732 i va fer efectius diversos decrets religiosos però els costums tradicionals hindús van continuar tenint un lloc important i principal als afers culturals.
L'arribada dels anglesos durant les guerres europees napoleòniques va augmentar l'interès dels europeus en Kutai. Els exploradors i oficials militars que van visitar el sultanat, van escriure sobre la seva cultura única. Es van establir relacions comercials que van ser encoratjades pels comerciants britànics a Singapur. No obstant no fou fins al 1825 que es van establir relacions polítiques permanents amb el sultà, i els holandesos van proclamar el protectorat (8 d'agost). El 23 de juliol de 1845, a la mort del sultà Muhammad Salehuddin bin Aliuddin, els holandesos van designar un administrador civil local. Durant i després de la guerra de Banjarmasin de 1859-1863 el govern de les Índies Orientals Holandeses va augmentar el seu control sobre el territori i sobre tot Borneo a través d'un sistema de tractats amb els sobirans locals.
Al final del segle xix i començament del XX la zona costanera de Borneo es va desenvolupar de manera ràpida i Kutai en fou el més gran beneficiat, especialment després del descobriment de rics pous de petroli. La tresoreria local va augmentar mercès al petroli i a les mines i també a l'augment del comerç. Des de 1920 la tresoreria del sultà tenia un gran superàvit i va esdevenir un prestador a altres estats natius i al mateix govern neerlandès de les Índies Orientals. En aquest temps es va construir el palau reial, exemple d'Art Deco als tropics.
A la segona Guerra Mundial el sultanat va patir molt; el petroli fou disputat per japonesos i aliats. Però Kutai es va lliurar de les principals malifetes japoneses que van afectar altres estats entre 1943 i 1944. Les batalles de Balikpapan i Samaranda van quedar per l'honor de les unitats britàniques que hi van participar.
Kutai va esdevenir part de l'estat federal de Siak (o Gran Siak) el 1947 però el 1948 va ingressar a l'estat de Kalimantan Timur. El 1950 va esdevenir una monarquia autònoma dins d'Indonèsia. Aquest estatus fou abolit pel govern indonesi el 21 de gener de 1960 quan el sultà Adji Muhammad Parikesit (+1981) fou declarat deposat. La família reial va conservar una alta consideració i respecte dels seus antics súbdits. Això va molestar al govern que va iniciar un període d'intimidació i va arrestar al sultà i a membres de la seva família; els vestits i uniformes reials foren cremats, el palau confiscat (i convertit en museu) i la família reial expulsada. Això no va fer minvar la gran consideració del poble sobre els seus sobirans; una llarga campanya per la restauració iniciada el 1970 va culminar el 1999 amb l'acceptació pel govern del restabliment de l'antic sultanat. El fill gran del darrer sultà, Haji Adji Muhammad Salehuddin II, de 76 anys, fou instal·lat solemnement el 22 de setembre de 2001. Aquesta restauració tenia sentit cultural i no polític; el seu títol complet és Sa Excel·lència Sri Paduka Sultan Haji Aji (nom de regnat i personal) al-Adil ul-Muminin Khalifat, sultà de Kutai Karta Negara, i el tractament és de Son Altessa.
S'ha de distingir entre les banderes abans de 1960 i les posteriors al 2001. Abans del 1960 es coneix un estendard dinàstic groc, quadrat, amb l'escut reial. A més existien tres banderes més: bandera groga amb tigre (el dibuix difereix segons el model) amb corona sobre el cap i sense; la que portava la corona era l'estendard reial; sense corona era la bandera de l'estat; i un tercer model era una insígnia reial triangular groga (amb una estreta banda vertical al pal) amb l'espasa de dues puntes en daurat.
La bandera moderna és groga amb el tigre amb corona i és essencialment un estendard reial. El disseny del tigre és lleugerament diferent.