La sfârșitul secolului al XVIII-lea, coloniștii albi au început să migreze din cele treisprezece colonii originale peste Munții Apalași și în „Vest”. La începutul secolului al XIX-lea, ei au început încet să se mute în părțile estice ale Teritoriului de Nord-Vest, care fusese înființat în 1787, și în părți din Vechiul Sud-Vest, sau Alabama, Mississippi și vestul Kentucky și Tennessee. Ei vedeau popoarele native care locuiau acolo ca pe un obstacol care trebuia cucerit sau împins mai departe spre vest.
Statele Unite au negociat Achiziția Louisiana în 1803. Deși granițele au rămas nedefinite până la Tratatul Adams-Onís din 1819, după 1803 râul Mississippi nu a mai servit drept graniță vestică a națiunii. Exploratorii acestei uriașe porțiuni americane din vestul trans-Mississippi au dezvăluit că partea estică era fertilă și locuibilă. Partea central-vestică, văzută de unii ca fiind „Marele Deșert American”, era considerată nelocuibilă.
Președintele Thomas Jefferson și cei care l-au urmat au imaginat o „zonă de colonizare indiană” sau o frontieră indiană permanentă, într-un palier nord-sud pe malul vestic al Mississippi. Mulți oameni au susținut această abordare a „problemei indienilor”. Aceștia credeau că mutarea indienilor în acea zonă ar fi rezolvat definitiv conflictul dintre locuitorii nativi originali și euroamericanii care clamau să „civilizeze” continentul. Albii urmau să trăiască la est de râu, iar indienii la vest de acesta. Un susținător vocal al unei zone indiene trans-Mississippi a fost misionarul baptist Isaac McCoy, care credea că, în cele din urmă, regiunea ar trebui să devină un teritoriu oficial, cu guvern și legi, pentru toți indienii. Conceptul unei zone indiene s-a consolidat în timpul administrației președintelui John Quincy Adams și s-a dezvoltat ulterior pe deplin sub conducerea președintelui Andrew Jackson. O regiune concepută ca „țara indienilor” a fost precizată în 1825 ca fiind tot teritoriul aflat la vest de Mississippi. În cele din urmă, țara indienilor sau Teritoriul indian avea să cuprindă actualele state Oklahoma, Kansas, Nebraska și o parte din Iowa.
În realitate, procesul de mutare a indienilor a început prin tratate la scurt timp după 1800. În plus, multe triburi au fugit pur și simplu spre vest pe măsură ce linia de colonizare a albilor avansa spre și apoi peste râul Mississippi. Unii dintre Cherokee, de exemplu, începuseră să se deplaseze spre vest în anii 1810, cu mari migrații în partea central-vestică a Arkansasului în 1817, într-o regiune pe care o schimbaseră pentru pământ în sud-est. Cu puțin timp înainte de tratatul Cherokee din 1817 a avut loc „Lovely’s Purchase” în 1816, iar un tratat Osage din 1818 a eliberat teoretic nord-estul Oklahomei și a adăugat terenul la domeniul public. În 1820, Choctaw au fost de acord să accepte terenul dintre râurile Arkansas și Canadian și Red River, în actuala Oklahoma.
Între timp, albii au traversat și ei Mississippi și au început să ocupe o fâșie largă care se întinde de la nord la sud de-a lungul laturii sale vestice. În curând dens populat, Missouri a devenit stat în 1821, iar Arkansas un teritoriu în 1819. În 1824 a fost trasată o graniță vestică pentru Arkansas, care a inclus total sau parțial comitatele Craig, Mayes, Delaware, Adair, Cherokee, Sequoyah, Muskogee, Wagoner, Haskell, Le Flore, Latimer, Choctaw, Pushmataha și McCurtain din actualele comitate Oklahoma. De asemenea, a încorporat cesiunea Osage din 1816 din Lovely’s Purchase, precum și o mare parte din terenul promis Choctaw în tratatul din 1820. Încă din 1816, albii începuseră să se stabilească în această fâșie de pământ, care, în 1820, a fost încorporată de Teritoriul Arkansas în comitatul Crawford, la nord, și în comitatul Miller, la sud, extinzându-se chiar până în nord-estul Texasului actual. În 1827, comitatul Lovely a fost creat din comitatul Crawford, cuprinzând aproape tot nord-estul actual al Oklahomei, iar sediul său a fost stabilit la Lovely Courthouse (Nicksville), mai târziu locația Misiunii Dwight din comitatul Sequoyah.
Cerokee de Vest s-au opus faptului că erau înconjurați de albi și de comitatele organizate din Arkansas. Choctaw s-au opus, de asemenea, comitatului Miller și rezidenților săi albi. În 1825, un nou tratat a ajustat granița estică a Choctaw, iar comitatul Miller a fost redus. Mulți albi care se stabiliseră în acea regiune s-au mutat acum la est de noua linie. În 1828, guvernul federal s-a folosit de această situație pentru a pune la cale un alt tratat cu cherokeii din vest, prin care aceștia au fost de acord să se mute la vest de noua linie. Comitatul Lovely a fost desființat, iar granița dintre Arkansas și Teritoriul Indian, de fapt națiunile Choctaw și Cherokee, a fost redesenată în 1828, în general de-a lungul graniței actuale dintre Oklahoma și Arkansas.
În timpul anilor 1820 și 1830, zeci de triburi din nord-estul, vestul mijlociu și sud-estul țării au fost îndepărtate prin tratat și în temeiul Legii de îndepărtare a indienilor din 1830, care îl autoriza pe președinte să forțeze triburile să cedeze pământurile lor la est de Mississippi. Cei care au făcut acest lucru urmau să fie plasați la vest de noile așezări albe, adică la vest de Meridianul 95. O lege comercială din 1834 a definit în continuare „ținutul indienilor” ca fiind toată acea parte a Statelor Unite aflată la vest de Mississippi și care nu se află în statele Missouri, Louisiana sau Arkansas Territory, sau în orice alt teritoriu organizat. Albii au fost excluși cu grijă din această regiune, în majoritatea scopurilor, iar comerțul acestora cu indienii a fost reglementat. În scopuri juridice, regiunea nordică (în cea mai mare parte actualul Kansas) a fost atașată de Missouri, iar partea sudică (în cea mai mare parte actualul Oklahoma) de Teritoriul Arkansas (după 1836, statul Arkansas). În 1835, Isaac McCoy se pare că a folosit pentru prima dată în presa scrisă cuvintele „Teritoriul indian”.
Creek, Seminole și Chickasaw au cedat, de asemenea, în fața migrației forțate. Toate aceste triburi din sud-estul țării au locuit ulterior în partea de sud a „Teritoriului Indian”. În mod similar, numeroase triburi din Nord-Est și din Teritoriul de Nord-Vest, inclusiv Kickapoo, Miami, Delaware și Shawnee, au fost mutate în partea de nord, actualul Kansas. Astfel, până în 1840, Teritoriul Indian fusese populat, în mod rar, de grupuri de nativi, dar nu era un teritoriu oficial sau organizat.
Cu toate acestea, pentru că terenurile sale fertile s-au dovedit a fi dezirabile pentru albi, prin Legea Kansas și Nebraska din 1854, Congresul a organizat în mod oficial acele părți din nordul Teritoriului Indian în teritorii oficiale care au devenit ulterior state. (Kansas a intrat în Uniune în 1861, iar Nebraska în 1867.) După încheierea Războiului Civil, indienii au fost mutați mai la sud, în partea din Teritoriul Indian care este actualul Oklahoma. Triburile de câmpie, inclusiv Cheyenne, Arapaho, Comanche, Kiowa și Apache, au fost concentrate în rezervații în jumătatea vestică a teritoriului. Până în 1889, mai mult de trei duzini de triburi își aveau reședința aici.
Pentru a înțelege sensul deplin al termenului „Teritoriul Indian”, trebuie să înțelegem și procesul prin care o regiune a devenit teritoriu. Așa cum a fost stabilit de legislația Statelor Unite, începând cu Ordonanța de Nord-Vest din 1787, atunci când o parte definită în mod specific din domeniul federal neorganizat era suficient de populată, rezidenții săi (cetățeni ai Statelor Unite) puteau adresa o petiție Congresului pentru obținerea statutului de teritoriu. Ulterior, Congresul urma să adopte o lege organică, cu o declarație de drepturi pentru rezidenții teritoriului, și să înființeze un guvern tripartit, cu ramuri executive și judiciare numite. Rezidenții au ales o ramură legislativă. Guvernul federal avea autoritatea supremă asupra afacerilor teritoriale, iar în Congres a fost ales un reprezentant teritorial. Congresul nu a adoptat niciodată o lege organică pentru Teritoriul Indian, deși au fost propuse câteva măsuri și a fost redactat un proiect de lege în acest scop. Regiunea nu a avut niciodată un guvern oficial și a rămas neorganizată. Prin urmare, locația geografică numită în mod obișnuit „Teritoriul Indian” nu era un teritoriu.
La sfârșitul secolului al XIX-lea, guvernul federal a început să își asume un control mai mare asupra evenimentelor care se desfășurau în ținutul indian. În martie 1889, o lege a înființat un sistem judiciar federal cu sediul la Muskogee, asumându-și autoritatea și jurisdicția judiciară care fusese exercitată, începând cu Legea comerțului din 1834, de către Districtul de Vest din Arkansas. Măsura din 1889 a specificat pentru prima dată granițele închise pentru Teritoriul Indian, redus acum în mod oficial la o zonă delimitată de Texas la sud, Arkansas și Missouri la est, Kansas la nord și Teritoriul New Mexico la vest.
În curând, această zonă a fost redusă din nou atunci când Teritoriul Oklahoma a fost creat dintr-o parte a acestuia prin Actul Organic din mai 1890. A fost numit un guvernator și au fost înființate o adunare teritorială cu două camere și un sistem judiciar. Teritoriu de bună credință al Statelor Unite, Teritoriul Oklahoma ar fi fost eligibil pentru statutul de stat dacă populația sa ar fi crescut suficient de mult și dacă liderii săi ar fi urmat procesul prescris de legea federală. Legea organică a Teritoriului Oklahoma a definit și mai precis Teritoriul Indian, reducându-l la puțin mai mult decât jumătatea estică a actualului stat. În cadrul Convenției Sequoyah din 1905, liderii indieni au încercat să ocolească procesul teritorial și să obțină statutul de stat separat pentru Teritoriul Indian. Cu toate acestea, odată cu unirea din 1907 a națiunilor indiene și a Teritoriului Oklahoma sub numele de Statul Oklahoma, un teritoriu sau un stat separat, dominat de indieni, nu mai era viabil. Pe parcursul secolului XX, termenul generic „Teritoriul Indian” a ajuns să fie folosit de istorici, genealogiști și de public pentru a reprezenta întreaga regiune Oklahoma în timpul perioadei de preconstituire.
.