Minjar á Oklahoma-svæðinu benda til búsetu manna fyrir 10.000-15.000 árum.  Talað er um Clovis- og folsom-menningu í þessu sambandi.  Þarna voru veiðimenn, sem lifðu á vísundum og annarri bráð, sem nóg var af á sléttunum.  Síðari menningarsamfélög skildu eftir sig fagra leirmuni, vefnað, höggmyndir og málmhluti og höfðu komið sér upp velþróuðum samgöngunetum.

Fyrsti Evrópumaðurinn á svæðinu var spænski landkönnuðurinn Francisco Vásquez de Coronado (1541).  Franskir kaupmenn og gildruveiðimenn komu við á svæðinu á 16. og 17. öld.  Árið 1803 varð Oklahoma-svæðið (nema mjóa ræman og allravestasti hluti núverandi fylkis) eign BNA við Louisianakaupsamningana.  Árið 1817 hóf sambandsstjórnin nauðungarflutninga stórra hópa indíána frá Alabama, Georgíu, Flórída og Mississippi til svæðisins.  Oklahoma var skipt milli creek-, cherokee-, chickasaw-, choctaw- og seminole-indíána.  Árið 1834 var það lýst verndarsvæði indíána og yfirráð þjóðflokkanna tryggð.

Í borgara/þrælastríðinu stóðu margir indíánar, sem áttu þræla, með Suðurríkjunum.  Eftir stríðið voru indíánar knúðir til að skrifa undir ýmsa samninga á árabilinu 1866-83, sem leyfðu flutning fleiri indíánaættkvísla inn á svæðið vestanvert.  Stór svæði voru enn ónumin og hvítum mönnum var stranglega bannað landnám.  Engu að síður voru uppi margar áætlanir um landnám meðal hvítra hópa, sem leiddu til skýrrar yfirlýsinga Rutherford B. Hayes, forseta, árin 1789 og 1880,sem staðfestu landnámsbannið.  Þessi bannlög voru oft brotin og þrýstingur á stjórnvöld um opnun svæðisins til landnáms jókst stöðugt.  Árið 1885 samþykkti sambandsþingið, að forseti landsins gæti hafið samningaviðræður við creek- og seminole-indíánana um landnám á ónumdum svæðum í Oklahoma.  Þessum samningaviðræðum lauk með góðum árangri 1889 og um hádegi hinn 22. apríl hófst kapphlaupið um beztu jarðirnar, svæðin og borgastæðin, þegar 50.000 manns flæddu inn í Oklahoma fyrsta daginn.  Tjaldborgir risu, búgarðar spruttu upp og íbúum fjölgaði ótrúlega hratt.

Sambandsstjórnin samþykkti stofnun fylkis 2. marz 1890 á suðurhluta svæðisins og vesturhluta indíánasvæðanna auk mjóu landræmunnar.  Meira land var opnað til landnáms árið 1906.  Hinn 16. nóvember 1907 sameinuðust bæði svæðin sem 46. fylki BNA.

20. öldin.  Efnahagslífið var mjög óstöðugt og sveiflukennt fram undir miðja öldina.  Olíuframleiðsla varð æ mikilvægari og verð búvöru hrapaði þar til eftirspurn óx í fyrri- og síðari heimstyrjöldinni og jafnvægi komst á.  Ekki var unnt að nýta nýuppgötvaðar olíu- og gasbirgðir í jörðu á þriðja áratugnum vegna heimskreppunnar, sem þurrkar og uppskerubrestur gerðu enn alvarlegri.  Á sjötta áratugnum var gripið til áhrifaríkra aðgerða til jarðvegsbóta og flóðavarna.  Nýjum iðnaði á mörgum sviðum var komið á fót (rafeindaiðnaður, geimferðatæki, plast og húsbílaframleiðsla).  Lækkandi olíu- og gasverð leiddi til efnahagsvanda á síðari hluta níunda og fyrri hluta tíunda áratugarins.