Kukaiņu, tāpat kā daudzu citu bezmugurkaulnieku grupu evolūcijas vēsture ir slikti izprotama. Daudzus gadu desmitus tika uzskatīts, ka tie atzarojas no tūkstoškājām un simtkājiem, kas, kā zināms, kolonizēja zemi jau pirms 428 miljoniem gadu Silūra periodā. Taču jaunākie ģenētiskie pētījumi liecina, ka kukaiņi, visticamāk, atdalījās no vēžveidīgajiem pirms aptuveni 410 miljoniem gadu. Šo evolūcijas pārmaiņu apstākļi ir diskutējami, un tie ir daudz mazāk skaidri nekā daivu zivju evolūcija par primitīviem tetrapodiem.
Agrākais zināmais paraugs kukaiņu vēsturē ir devona fosilija Rhyniognatha hirsti, kas datēta pirms 396 līdz 407 miljoniem gadu. Tas tika atrasts Rhynie Chert veidojumā, labi saglabājusies devona ekosistēmā, kurā ir daži no pirmajiem sauszemes augiem ar vaskulārajiem audiem un viena no agrākajām un vislabāk saglabātajām sauszemes posmkāju fosilijām. Šī kukaiņa apakšžokļi liecina, ka tas jau bija attīstījis lidojumu, slēpot kukaiņu lidojumu izcelsmi un citus svarīgus kukaiņu vēstures aspektus.
Kad un kā lidojums iekļuva kukaiņu vēsturē, ir slikti izprotams. Viens pētnieks Džims Mārdens ir iepazīstinājis ar modeli, kurā kukaiņu lidojums attīstījās no evolucionāri adaptīviem starpposmiem, kas ietvēra nosmelšanu uz ūdens. Viņš norāda uz akmeņmušām, dzīvu kukaiņu grupu, kas izmanto spārnus, lai skenētu pa ūdens virsmu. Ir atrastas sugas, kurās tiek izmantotas ūdens nosmelšanas šķirnes, kurām ir arvien mazāks faktiskais kontakts ar ūdeni, katrs solis sniedz ievērojamas priekšrocības ātruma ziņā un tādējādi spēju izvairīties no plēsējiem un meklēt barības avotus.
Ir zināmas vairākas seškāju (seškājainu bezmugurkaulnieku) grupas, kas evolucionāri ir balstītas uz kukaiņiem un būtu no tiem atdalījušās pirms aptuveni 400 miljoniem gadu, kad parādījās pirmie fosilie kukaiņi. Tajos ietilpst bagātīgās atsperes, kā arī mazāk atpazītie proturāni un diplurāni. Tiek uzskatīts, ka atsperastes, proturāni un diplurāni attīstīja savu seškāju pārvietošanās formu neatkarīgi viens no otra, bet tikai kukaiņi ieguva spēju lidot.
Desmitiem miljonu gadu kukaiņi un citi mazi bezmugurkaulnieki bija vienīgie dzīvnieki, kas kolonizēja zemi, tolaik tos klāja īsi augi, kas nepārsniedza vidukļa augstumu. Augiem augot un zivju cilts evolūcijai veidojoties pirmajiem abiniekiem, kukaiņiem pievienojās lielāki tetrapodi, kas tos būtu patērējuši lielā skaitā, lai izdzīvotu. Tomēr, pateicoties oglekļa perioda augstajam skābekļa līmenim, pirms aptuveni 320 miljoniem gadu daži kukaiņi izauga līdz milzīgiem izmēriem, piemēram, grifs Meganeura, kam bija divu pēdu spārnu platums. Bet, kad skābekļa līmenis pazeminājās, šie kukaiņi nekavējoties nomira, jo nespēja cirkulēt pietiekami daudz skābekļa caur savu ķermeni.
Nākamie lielie pavērsieni kukaiņu vēsturē notika visā mezozoja periodā, kad attīstījās lielākā daļa mūsdienu grupu, kā mēs tās zinām. Apmēram pirms 120 miljoniem gadu attīstījās ziedoši augi, un sadarbība starp kukaiņiem (īpaši bitēm) un šiem jaunpienācējiem radīja abpusēji izdevīgas evolūcijas attiecības. Rezultātā ziedoši augi tagad ir dominējošā sauszemes flora.