「オクラホマ」という名前はokla と hummaを合わせたものであり、「赤い人々」を意味する。チョクトー族の酋長アレン・ライトが、インディアン準州の利用に関するアメリカ合衆国政府との条約交渉中の1866年に提案したものである。ライトはアメリカ合衆国インディアン問題監督官が支配する、全てインディアンの州を構想していた。okla hummaという言葉はアメリカインディアン全体を指すときに使われるチョクトー語である。後にオクラホマ準州として事実上の地域の名称となり、この地域が白人開拓者に開放されてから2年後の1890年には公式の名称となった[4][10][11]。
歴史詳細は「オクラホマ州の歴史」を参照

最終氷期にはインディアンがオクラホマを通って移動したという証拠が存在するが[12]、最初の恒久的な住人となると、紀元850年から1450年にアーカンソー州境近くに塚のような構造物を築いた人々である[13][14]。スペイン人フランシスコ・バスケス・デ・コロナドが1541年に州内を旅したが[15]、1700年代にフランス人探検家達が地域の領有権を主張した[16]。フランスによる領有は、1803年のルイジアナ買収によってアメリカ合衆国がミシシッピ川の西側領土全てをフランスから購入するまで続いた[15]。

1794年のフォールン・ティンバーズの戦いの講和条約としてグリーンヴィル条約（英語版）（1795年8月3日）が締結されると、19世紀前半に北アメリカ中のインディアンが先祖伝来の土地を追い出され（Treaty of Dancing Rabbit Creek）、現在のオクラホマ州周辺の地に移動させられた。チョクトー族は、アメリカ合衆国南東部から移動させられた文明化五部族の中では最初の部族だった。「涙の道」ということばは1831年のチョクトー族の移動に端を発する言葉だったが、通常はチェロキー族の移動を表すときに使われている[17]。約17,000人のチェロキー族と彼等が所有していた2,000人の黒人奴隷がその故郷から移動させられた[18]。オクラホマの地域は既にオーセージ族やクアポー族に占められていたが、チョクトー族のための土地と呼ばれ、その後インディアンの土地となり、さらにアメリカ合衆国の政策でその他のインディアン部族を含むようにその境界が再定義された。1890年までに30以上の部族がインディアン準州（あるいは「インディアン・カントリー」と呼ばれる）領域に集中させられた[19]。南北戦争の間、多くのインディアンが北軍または南軍に従軍した。チェロキー族の場合は部族内抗争も起こった[20]。オクラホマの奴隷制度は1866年になって廃止された[21]。

1866年から1899年[15]、テキサス州の牛牧場経営者が東部の都市での食糧需要に応ずるために、カンザス州の鉄道まで約束した配達期限に牛を届けられるよう牛を追わせた。カウボーイが牛を北に追い、あるいはインディアン準州の中に違法に入植することで牛追い道と牛牧場が発展した[15]。1881年、主要な牛追い道5本（Goodnight?Loving Trail、Potter-Bacon trail、ウェスタン・トレイル（英語版）、チザム・トレイル（英語版）、Shawnee Trail）のうち4本がインディアン準州内を抜けていた[22]。

インディアン準州内に白人開拓者が増えたことで、アメリカ合衆国政府は1887年にドーズ法を制定し、部族の土地を個々の家族単位に割り当て、農業と土地の私有を奨励したが、連邦政府の土地も確保した。この過程で、鉄道会社が準州内のインディアンが所有していた土地の半分近くを取り上げ、外部から来る開拓者が購入できるように確保した[23]。通常、土地は最初にその土地に来た開拓者に開放された。ランドラッシュと呼ばれる、決められた時刻に特定の土地が開拓者に開放され、待ちかねた開拓者が一斉に駆け出すような仕組みが1889年のものを含め何度か行われた。公式の解放時刻以前に境界を越えるという規則破りは「抜け駆け」（sooner）で境界を越えたと言われるようになり、このsooner（早い者勝ち）という言葉がオクラホマ州の公式ニックネーム（Sooner State）にもなった[24]。準州を州に昇格させる動きは19世紀末近くに始まった。このころ、カーティス法（英語版）でインディアン部族に対する土地の割り当てを続けていた。オクラホマと名付ける全てインディアンの州を創設する試みや、セコイアと名付けるやはり全てインディアンの州を創設する試みが次々と失敗したが、1905年のセコイア州憲法制定会議がその2年後のオクラホマ州憲法制定会議の基になった[25]。1907年11月16日、オクラホマはアメリカ合衆国46番目の州に昇格した。

この新州で石油が発見されて折からの石油ブームの焦点となり、町は急速に人口を増やして富を掴んだ。タルサ市は20世紀の大半の期間「世界の石油首都」と呼ばれており、油田の探査で州の初期経済を潤わせた[26]。1927年、「国道66号線の父」とも呼ばれたオクラホマの事業家サイラス・アベリー（英語版）が、アメリカ国道66号線の建設に関わる運動を始めた。アベリーは、テキサス州アマリロからタルサ市に伸びていた道路を用いて66号線を建設するために、本拠地のタルサ市で66号線協会を結成し、その計画を監督した[27]。

オクラホマはアフリカ系アメリカ人の歴史も豊富である。20世紀初期には近隣の特にカンザス州などから黒人開拓者が移住してきたために、多くの黒人町が繁栄した。政治家のエドワード・P・マッケイブが当時のインディアン準州に黒人開拓者が来ることを奨励した。マッケイブはセオドア・ルーズベルト大統領と、オクラホマを黒人多数の州にする可能性を検討した。20世紀初期までに、タルサ市のグリーンウッド地区は、アメリカ合衆国の中でも最も繁栄するアフリカ系アメリカ人社会の1つになった[28]。20世紀への変わり目以後、ジム・クロウ法によって人種差別が激しくなったが、黒人は繁栄する地域を作り上げた。1915年以降のクー・クラックス・クランの復活によって社会の緊張が高まった。1921年には白人が黒人を攻撃する事件があり、タルサ人種虐殺と呼ばれた。この事件では、16時間におよぶ暴動で市街地35ブロックが破壊され、被害総額は180万ドル、死者は300人とされる、アメリカ史の中でも最大級の人種間暴力事件となった[29]。1920年代後半までに州内ではクー・クラックス・クランの勢いが衰え、無視できる状態になった[30]。1930年代に起こったダストボウル、多くの農家を貧窮に追いやった

1930年代は、オクラホマ州の一部はお粗末な耕作法、うち続く干ばつと強風のために苦難の時となった。カンザス州、テキサス州、ニューメキシコ州およびオクラホマ州北西部におきたダストボウルは、長い期間の小雨と異常な高温の産物であり、数多い農家が貧窮の底に沈み、アメリカ合衆国西部の肥沃な土地への再移住を強いられることになった[31]。1950年までの20年間は、オクラホマ州人口が6.9%減少し、人口が減った唯一の期間となった。

土壌と水の保全計画によって州内の農耕法が著しく変化し、大規模な洪水制御系とダムが建設された。多くの貯水池と人工湖が造られ家庭用と農業用の水が供給された。1960年代までに、200以上の湖が建造され、国内でも最大数となった[32][33]。オクラホマシティの爆破されたアルフレッド・P・ムラー連邦ビル

1995年、アメリカ史の中でも最悪のテロ事件の舞台となった。1995年4月19日にオクラホマシティのアルフレッド・P・マラー連邦ビル前で爆発が起こり、19人の子供を含む168人が殺された。爆破犯人はティモシー・マクベイとテリー・ニコルズとされ、マクベイは死刑を宣告され2001年6月11日に、連邦政府によって処刑された。相棒のニコルズは釈放の可能性の無い終身刑とされ、現在も服役中である[34]。