I slutningen af det attende århundrede begyndte hvide bosættere at vandre fra de oprindelige tretten kolonier over Appalacherne og ind i “Vesten”. Omkring århundredeskiftet begyndte de langsomt at bevæge sig ind i de østlige dele af Northwest Territory, som var blevet oprettet i 1787, og ind i dele af det gamle sydvestlige område, eller Alabama, Mississippi og det vestlige Kentucky og Tennessee. De betragtede de indfødte folk, der boede der, som en hindring, der skulle erobres eller skubbes længere mod vest.
Der blev forhandlet om Louisiana-købet i 1803 af USA. Selv om grænserne forblev udefinerede indtil Adams-Onís-traktaten i 1819, fungerede Mississippifloden efter 1803 ikke længere som nationens vestlige grænse. Udforskere af denne enorme amerikanske del af det trans-Mississippi vestlige område afslørede, at den østlige del var frugtbar og beboelig. Den midtvestlige del, der af nogle blev betragtet som den “store amerikanske ørken”, blev anset for ubeboelig.
Pres. Thomas Jefferson og hans efterfølgere forestillede sig en “indiansk koloniseringszone” eller en permanent indiansk grænse i et nord-sydgående lag på Mississippis vestlige bred. Mange mennesker gik ind for denne tilgang til “det indianske problem”. De mente, at en flytning af indianerne til dette område permanent ville løse konflikten mellem de oprindelige indfødte indbyggere og de euroamerikanere, der skreg efter at “civilisere” kontinentet. De hvide skulle bo øst for floden og indianerne vest for den. En af de store fortalere for et indianerområde på tværs af Mississippi var baptistmissionæren Isaac McCoy, som mente, at regionen med tiden skulle blive et officielt territorium med regering og love for alle indianere. Konceptet om et indianerområde blev styrket under præsident John Quincy Adams’ administration og udviklede sig senere fuldt ud under præsident Andrew Jacksons ledelse. Et område, der blev opfattet som “indianerlandet”, blev i 1825 specificeret som alt det land, der ligger vest for Mississippi. I sidste ende skulle indianerlandet eller indianerterritoriet omfatte de nuværende stater Oklahoma, Kansas, Nebraska og en del af Iowa.
I virkeligheden var processen med fjernelse af indianerne blevet indledt ved traktater kort efter 1800. Desuden flygtede mange stammer simpelthen mod vest, efterhånden som den hvide bosættelseslinje rykkede frem mod og derefter over Mississippi-floden. Nogle af cherokeeerne var f.eks. begyndt at bevæge sig mod vest i 1810’erne, med store vandringer ind i det vestlige centrale Arkansas i 1817 til et område, som de havde byttet for land i det sydøstlige Arkansas. Kort før Cherokee-traktaten fra 1817 kom “Lovely’s Purchase” i 1816, og en Osage-traktat fra 1818 ryddede teoretisk set det nordøstlige Oklahoma og tilføjede landet til det offentlige område. I 1820 indvilligede choktawerne i at acceptere land mellem Arkansas- og Canadian-floderne og Red River i det nuværende Oklahoma.
I mellemtiden krydsede de hvide også Mississippi og begyndte at besætte en bred stribe, der løb i nord-sydgående retning langs dens vestlige side. Missouri blev snart tæt befolket og blev en stat i 1821 og Arkansas et territorium i 1819. I 1824 blev der udstukket en vestlig grænse for Arkansas, og den omfattede hele eller dele af Craig, Mayes, Delaware, Adair, Cherokee, Sequoyah, Muskogee, Wagoner, Haskell, Le Flore, Latimer, Choctaw, Pushmataha og McCurtain counties i det nuværende Oklahoma. Den omfattede også Osage-området Lovely’s Purchase fra 1816 samt en stor del af det land, der blev lovet til Choctaw-folket i traktaten fra 1820. Allerede i 1816 var hvide begyndt at bosætte sig i denne landstrimmel, som i 1820 blev indlemmet af Arkansas Territory i Crawford County i nord og Miller County i syd, og som endda strakte sig ned i det nuværende nordøstlige Texas. I 1827 blev Lovely County oprettet fra Crawford County, der omfattede næsten hele det nuværende nordøstlige Oklahoma, og dets hovedsæde blev oprettet ved Lovely Courthouse (Nicksville), senere placeringen af Dwight Mission i Sequoyah County.
De vestlige Cherokee protesterede mod at være omgivet af hvide og af organiserede Arkansas amter. Choctaw’erne gjorde også indsigelse mod Miller County og dets hvide indbyggere. I 1825 justerede en ny traktat Choctaw’s østlige grænse, og Miller County blev reduceret. Mange hvide, der havde bosat sig i denne region, flyttede nu øst for den nye linje. I 1828 udnyttede den føderale regering situationen til at indgå endnu en traktat med de vestlige cherokesere, hvori de indvilligede i at flytte vest for den nye linje. Lovely County blev afskaffet, og grænsen mellem Arkansas og Indian Territory, som i virkeligheden var Choctaw- og Cherokee-nationerne, blev i 1828 genudmålt generelt langs den nuværende grænse mellem Oklahoma og Arkansas.
I løbet af 1820’erne og 1830’erne blev snesevis af stammer fra det nordøstlige, midtvestlige og sydøstlige område fjernet ved traktat og i henhold til Indian Removal Act fra 1830, som bemyndigede præsidenten til at tvinge stammerne til at afstå deres land øst for Mississippi. De, der gjorde det, skulle placeres vest for de nye hvide bosættelser, dvs. vest for den 95. meridian. I en handelslov fra 1834 blev “indianerlandet” yderligere defineret som hele den del af USA, der ligger vest for Mississippi og ikke i delstaterne Missouri, Louisiana eller Arkansas-territoriet eller andre organiserede territorier. Hvide blev omhyggeligt udelukket fra området til de fleste formål, og deres handel med indianere blev reguleret. Af juridiske årsager blev den nordlige region (hovedsagelig det nuværende Kansas) knyttet til Missouri og den sydlige del (hovedsagelig det nuværende Oklahoma) til Arkansas Territory (efter 1836 til staten Arkansas). I 1835 brugte Isaac McCoy tilsyneladende ordene “the Indian Territory” for første gang på tryk.
Creek, Seminole og Chickasaw bukkede også under for tvangsmigrationen. Alle disse sydøstlige stammer beboede herefter den sydlige del af “the Indian Territory”. På samme måde blev talrige stammer fra det nordøstlige og det nordvestlige territorium, herunder Kickapoo, Miami, Delaware og Shawnee, flyttet til den nordlige del, det nuværende Kansas. Således var Indian Territory i 1840 blevet befolket, sparsomt, af indfødte grupper, men var ikke et formelt eller organiseret territorium.
Da dets frugtbare jord imidlertid viste sig at være ønskværdigt for de hvide, organiserede Kongressen med Kansas og Nebraska-loven fra 1854 formelt de dele af det nordlige Indian Territory til officielle territorier, som senere blev til stater. (Kansas blev medlem af Unionen i 1861 og Nebraska i 1867.) Efter borgerkrigens afslutning blev indianerne flyttet længere sydpå til den del af indianerterritoriet, som er det nuværende Oklahoma. Plains-stammerne, herunder cheyenne-, arapaho-, comanche-, kiowa- og apache-stammerne, blev koncentreret i reservater i den vestlige halvdel af territoriet. I 1889 var mere end tre dusin stammer bosat her.
For at forstå den fulde betydning af udtrykket “the Indian Territory” må man også forstå den proces, hvorved en region blev til et territorium. Som fastlagt i amerikansk lov, der begyndte med Northwest Ordinance fra 1787, kunne indbyggerne (amerikanske statsborgere), når en specifikt defineret del af det uorganiserede føderale område var tilstrækkeligt befolket, anmode Kongressen om territorial status. Kongressen ville efterfølgende vedtage en organisk lov med en lov om rettigheder for indbyggerne i territoriet og oprette en tredelte regering med en udpeget udøvende og dømmende magt. Indbyggerne valgte en lovgivende gren. Den føderale regering havde den øverste myndighed over territoriale anliggender, og en valgt territorial repræsentant fik sæde i Kongressen. Kongressen vedtog aldrig en organisk lov for indianerterritoriet, selv om der blev foreslået et par foranstaltninger, og der blev skrevet et lovforslag med henblik herpå. Området fik aldrig en formel regering, og det forblev uorganiseret. Derfor var det geografiske sted, der almindeligvis kaldes “Indian Territory”, ikke et territorium.
I slutningen af det nittende århundrede begyndte den føderale regering at påtage sig mere kontrol over de begivenheder, der udspillede sig i indianerlandet. I marts 1889 blev der ved en lov oprettet et føderalt retssystem med base i Muskogee, hvorved man overtog den retslige myndighed og jurisdiktion, som siden handelsloven fra 1834 var blevet udøvet af Western District of Arkansas. Foranstaltningen fra 1889 specificerede for første gang lukkede grænser for Indian Territory, som nu officielt blev reduceret til et område, der var afgrænset af Texas i syd, Arkansas og Missouri i øst, Kansas i nord og New Mexico Territory i vest.
Snart blev dette område reduceret igen, da Oklahoma Territory blev oprettet fra en del af det ved den organiske lov i maj 1890. Der blev udnævnt en guvernør, og der blev oprettet en territorialforsamling med to huse og et retssystem. Oklahoma Territory var et ægte territorium i USA og ville være berettiget til at blive en stat, hvis dets befolkning voksede sig stor nok, og hvis dets ledere fulgte den proces, der var foreskrevet i den føderale lovgivning. Den organiske lov om Oklahoma Territory definerede Indian Territory endnu mere præcist og reducerede det til lidt mere end den østlige halvdel af den nuværende stat. På Sequoyah-konventet i 1905 forsøgte indianernes ledere at omgå den territoriale proces og opnå særskilt statsdannelse for Indian Territory. Men med foreningen i 1907 af indianernationerne og Oklahoma Territory som staten Oklahoma var et separat, indiansk domineret territorium eller stat ikke længere levedygtigt. I løbet af det tyvende århundrede kom det generiske udtryk “Indian Territory” til at blive brugt af historikere, slægtsforskere og offentligheden til at repræsentere hele Oklahoma-regionen i perioden før statsdannelsen.