I slutet av 1700-talet började vita bosättare vandra från de ursprungliga tretton kolonierna över Appalacherna och in i ”väst”. Runt sekelskiftet 1800 började de långsamt flytta in i de östra delarna av det nordvästra territoriet, som hade inrättats 1787, och i delar av den gamla sydvästern, eller Alabama, Mississippi och västra Kentucky och Tennessee. De betraktade de ursprungsbefolkningar som bodde där som ett hinder som skulle erövras eller drivas vidare västerut.
USA förhandlade fram Louisianaköpet 1803. Även om gränserna förblev odefinierade fram till 1819 års Adams-Onís-fördrag, fungerade Mississippifloden efter 1803 inte längre som nationens västra gräns. Utforskare av denna enorma amerikanska del av den trans-Mississippi västra delen avslöjade att den östra delen var bördig och beboelig. Den mellanvästra delen, som av vissa betraktades som ”den stora amerikanska öknen”, ansågs obeboelig.
President Thomas Jefferson och de som följde honom föreställde sig en ”indiankolonisationszon” eller en permanent indiangräns, i ett nord-sydligt skikt på Mississippis västra strand. Många förespråkade detta tillvägagångssätt för att lösa ”indianproblemet”. De trodde att en förflyttning av indianer till detta område permanent skulle lösa konflikten mellan de ursprungliga urinvånarna och de euroamerikaner som ville ”civilisera” kontinenten. De vita skulle bo öster om floden och indianerna väster om den. En uttalad förespråkare av ett indianområde över Mississippi var baptistmissionären Isaac McCoy, som ansåg att regionen så småningom skulle bli ett formellt territorium, med regering och lagar, för alla indianer. Konceptet med en indianzon befästes under president John Quincy Adams administration och utvecklades senare fullt ut under president Andrew Jacksons ledning. En region som tänktes som ”indianernas land” specificerades 1825 som allt land som ligger väster om Mississippi. Så småningom skulle indianlandet eller indianterritoriet omfatta de nuvarande delstaterna Oklahoma, Kansas, Nebraska och en del av Iowa.
I själva verket hade processen för indianförflyttning påbörjats genom fördrag strax efter 1800. Dessutom flydde många stammar helt enkelt västerut när den vita bosättningslinjen avancerade mot och sedan över Mississippifloden. En del av cherokeserna hade till exempel börjat flytta västerut på 1810-talet, med stora vandringar in i västra centrala Arkansas 1817 till en region som de hade bytt ut mot mark i sydöstra delen av landet. Strax före 1817 års Cherokee-avtal kom ”Lovely’s Purchase” 1816, och ett avtal med Osage från 1818 innebar teoretiskt sett att nordöstra Oklahoma rensades och att marken lades till det offentliga området. År 1820 gick choktawerna med på att acceptera mark mellan floderna Arkansas och Canadian River och Red River, i nuvarande Oklahoma.
Under tiden korsade de vita också Mississippi och började ockupera en bred remsa som löpte i nord-sydlig riktning längs dess västra sida. Missouri blev snart tätbefolkat och blev en delstat 1821 och Arkansas ett territorium 1819. År 1824 ritades en västlig gräns för Arkansas och den omfattade hela eller delar av Craig, Mayes, Delaware, Adair, Cherokee, Sequoyah, Muskogee, Wagoner, Haskell, Le Flore, Latimer, Choctaw, Pushmataha och McCurtain counties i nuvarande Oklahoma. Det innefattade också 1816 års Osage-överlåtelse av Lovely’s Purchase samt en stor del av det land som utlovades till Choctaw i 1820 års fördrag. Redan 1816 hade vita börjat bosätta sig i denna landremsa, som 1820 införlivades av Arkansas Territory i Crawford County, i norr, och Miller County, i söder, och som till och med sträckte sig ner i nuvarande nordöstra Texas. År 1827 skapades Lovely County från Crawford County, vilket innefattade nästan hela nuvarande nordöstra Oklahoma, och dess säte fastställdes vid Lovely Courthouse (Nicksville), senare platsen för Dwight Mission i Sequoyah County.
Den västra delen av cherokeefolket protesterade mot att vara omringade av vita och av organiserade Arkansas-landsting. Choctawerna motsatte sig också Miller County och dess vita invånare. År 1825 justerades Choctawernas östra gräns genom ett nytt fördrag och Miller County minskades. Många vita som hade bosatt sig i den regionen flyttade nu öster om den nya linjen. År 1828 utnyttjade den federala regeringen situationen för att få till stånd ett nytt fördrag med de västra cherokeserna där de gick med på att flytta väster om den nya linjen. Lovely County avskaffades och gränsen mellan Arkansas och Indian Territory, egentligen Choctaw- och Cherokee-folken, ritades om 1828 i stort sett längs den nuvarande gränsen mellan Oklahoma och Arkansas.
Under 1820- och 1830-talen förflyttades dussintals stammar från nordöstra, mellanvästra och sydöstra delen av landet genom avtal och i enlighet med 1830 års Indian Removal Act, som gav presidenten befogenhet att tvinga stammarna att avträda sina marker öster om Mississippi. De som gjorde det skulle placeras väster om de nya vita bosättningarna, det vill säga väster om 95:e meridianen. I en handelslag från 1834 definierades ”indianernas land” ytterligare som hela den del av Förenta staterna som ligger väster om Mississippi och som inte ligger inom delstaterna Missouri, Louisiana eller Arkansas Territory, eller något annat organiserat territorium. Vita var noggrant utestängda från området, för de flesta ändamål, och deras handel med indianer reglerades. För rättsliga ändamål knöts den norra regionen (huvudsakligen nuvarande Kansas) till Missouri och den södra delen (huvudsakligen nuvarande Oklahoma) till Arkansas Territory (efter 1836, delstaten Arkansas). År 1835 använde Isaac McCoy tydligen orden ”the Indian Territory” för första gången i tryck.
Creek, Seminole och Chickasaw gav också efter för tvångsmigrationen. Alla dessa sydöstra stammar bebodde därefter den södra delen av ”the Indian Territory”. På samma sätt förflyttades många stammar från nordöstra och nordvästra territoriet, däribland Kickapoo, Miami, Delaware och Shawnee, till den norra delen, nuvarande Kansas. År 1840 hade alltså Indian Territory befolkats, sparsamt, av indianska grupper men var inte ett formellt eller organiserat territorium.
Då dess bördiga mark visade sig vara åtråvärd för de vita, organiserade kongressen med 1854 års Kansas- och Nebraska-lag formellt de delar av norra Indian Territory till officiella territorier som senare blev delstater. (Kansas gick med i unionen 1861 och Nebraska 1867.) Efter inbördeskrigets slut flyttades indianerna längre söderut till den del av Indian Territory som är nuvarande Oklahoma. Plainstammarna, däribland cheyenne-, arapaho-, comanche-, kiowa- och apachestammarna, koncentrerades till reservat i den västra halvan av territoriet. År 1889 var mer än tre dussin stammar bosatta här.
För att förstå den fulla innebörden av begreppet ”Indian Territory” måste man också förstå den process genom vilken en region blev ett territorium. Enligt amerikansk lag, med början i Northwest Ordinance från 1787, kunde invånarna (amerikanska medborgare), när en specifikt definierad del av det oorganiserade federala området var tillräckligt befolkad, ansöka om territoriell status hos kongressen när en specifikt definierad del av det oorganiserade federala området var tillräckligt befolkad. Kongressen skulle därefter anta en organisk lag, med en stadga om rättigheter för territoriets invånare, och inrätta en tredelad regering med utsedda verkställande och dömande grenar. Invånarna valde en lagstiftande gren. Den federala regeringen hade den yttersta makten över territoriets angelägenheter, och en vald territoriell representant satt i kongressen. Kongressen antog aldrig någon organisk lag för indianterritoriet, även om några åtgärder föreslogs och ett lagförslag skrevs i detta syfte. Territoriet fick aldrig någon formell regering och förblev oorganiserat. Därför var den geografiska plats som vanligen kallas ”Indian Territory” inte ett territorium.
I slutet av 1800-talet började den federala regeringen ta på sig mer kontroll över händelser som utspelade sig i indianområdet. I mars 1889 inrättades genom en lag ett federalt domstolssystem med säte i Muskogee, vilket innebar att man övertog den rättsliga auktoritet och jurisdiktion som sedan 1834 års handelslag hade utövats av Western District of Arkansas. I 1889 års åtgärd angavs för första gången slutna gränser för Indian Territory, som nu officiellt reducerades till ett område som avgränsades av Texas i söder, Arkansas och Missouri i öster, Kansas i norr och New Mexico Territory i väster.
Snart reducerades detta område på nytt när Oklahoma Territory skapades från en del av det genom den organiska lagen i maj 1890. En guvernör utsågs och en territoriell församling med två hus och ett rättssystem inrättades. Som ett bona fide-territorium i Förenta staterna skulle Oklahoma Territory vara berättigat att bli delstat om dess befolkning blev tillräckligt stor och om dess ledare följde den process som föreskrivs i den federala lagen. I Oklahoma Territory Organic Act definierades Indian Territory ännu noggrannare och reducerades till något mer än den östra halvan av den nuvarande delstaten. Vid Sequoyahkonventet 1905 försökte de indianska ledarna kringgå den territoriella processen och få till stånd en separat delstat för Indian Territory. I och med att indiannationerna och Oklahoma Territory 1907 förenades till delstaten Oklahoma var det dock inte längre möjligt att skapa ett separat, indiandominerat territorium eller en separat delstat. Under 1900-talet kom den generiska termen ”Indian Territory” att användas av historiker, släktforskare och allmänheten för att representera hela Oklahomaregionen under den tid då indianerna var statsmedlemmar.