Evolucijska zgodovina žuželk, tako kot mnogih drugih skupin nevretenčarjev, je slabo razumljena. Dolga desetletja je veljalo, da se odcepijo od stonog in stonog, za katere je znano, da so kolonizirale zemljo že pred 428 milijoni let, v silurskem obdobju. Toda nedavne genetske študije kažejo, da so se žuželke bolj verjetno odcepile od rakov pred približno 410 milijoni let. Okoliščine te evolucijske spremembe so predmet razprave in veliko manj jasne kot evolucija rib z režnjami plavuti v primitivne tetrapode.
Najstarejši znani primerek v zgodovini žuželk je devonski fosil Rhyniognatha hirsti, datiran med 396 in 407 milijoni let. Najden je bil v formaciji Rhynie Chert, dobro ohranjenem devonskem ekosistemu, ki vključuje nekatere prve kopenske rastline z žilnim tkivom in med najzgodnejšimi in najbolje ohranjenimi fosili kopenskih členonožcev. Mandibule te žuželke kažejo, da je že razvila letenje, kar skriva izvor letenja žuželk in druge pomembne vidike zgodovine žuželk v skrivnost.
Točno, kdaj in kako je let vstopil v zgodovino žuželk, je slabo razumljeno. En raziskovalec, Jim Marden, je predstavil model, kjer se je let žuželk razvil iz evolucijsko prilagodljivih vmesnih korakov, ki vključujejo snemanje po vodi. Pokaže na kamne muhe, skupino živih žuželk, ki s svojimi krili leti po vodni površini. Ugotovljene so bile vrste, ki uporabljajo različne vrste odstranjevanja vode, ki imajo vse manj dejanskega stika z vodo, pri čemer vsak korak zagotavlja znatne koristi v smislu hitrosti in s tem zmožnosti izogibanja plenilcem in iskanja virov hrane.
Obstaja več znanih skupin heksapodov (šestnožnih nevretenčarjev), ki so evolucijsko bazalni za žuželke in bi se od njih odcepili pred približno 400 milijoni let, ko so se pojavile prve fosilne žuželke. Sem spadajo obilni pomladanci, pa tudi manj prepoznavni proturanci in dipluranci. Domneva se, da so pomladanci, proturanci in dipluranci razvili svojo heksapodno obliko gibanja neodvisno drug od drugega, vendar so le žuželke pridobile sposobnost letenja.
Več deset milijonov let so bile žuželke in drugi majhni nevretenčarji edine živali, ki so kolonizirale zemljo, takrat pa so jo pokrivale kratke rastline, ki niso bile višje od pasu. Ko so rastline rasle in se je vrsta rib razvila v prve dvoživke, so se žuželkam pridružili večji tetrapodi, ki bi jih za preživetje porabili v velikem številu. Vendar pa so zaradi visoke ravni kisika v obdobju karbona pred približno 320 milijoni let nekatere žuželke narasle do ogromnih velikosti, kot je beloglavi meganeura, ki je imel dva stopala razpon kril. Ko pa se je raven kisika znižala, so te žuželke takoj poginile zaradi nezmožnosti kroženja zadostne količine kisika po telesu.
Naslednji veliki mejniki v zgodovini žuželk so se zgodili skozi ves mezozoik, ko se je razvila večina sodobnih skupin, kot jih poznamo. Pred približno 120 milijoni let so se razvile cvetoče rastline in sodelovanje med žuželkami (zlasti čebelami) in temi prišleki je privedlo do obojestransko koristnega evolucijskega odnosa. Posledično so cvetoče rastline zdaj prevladujoča kopenska flora.