In de late achttiende eeuw begonnen blanke kolonisten vanuit de oorspronkelijke dertien kolonies over de Appalachen naar het “Westen” te trekken. Rond de eeuwwisseling van de negentiende eeuw begonnen zij zich langzaam te vestigen in de oostelijke delen van het Northwest Territory, dat in 1787 was gesticht, en in delen van het Oude Zuidwesten, of Alabama, Mississippi, en het westen van Kentucky en Tennessee. Zij beschouwden de inheemse volken die daar woonden als een obstakel dat moest worden veroverd of verder naar het westen moest worden geduwd.
De Verenigde Staten onderhandelden in 1803 over de aankoop van Louisiana. Hoewel de grenzen onduidelijk bleven tot het Adams-Onís Verdrag van 1819, diende de Mississippi rivier na 1803 niet langer als de westelijke grens van de natie. Ontdekkingsreizigers in dit enorme Amerikaanse deel van het trans-Missippi Westen ontdekten dat het oostelijke deel vruchtbaar en bewoonbaar was. Het midden-westelijk deel, door sommigen beschouwd als de “Grote Amerikaanse Woestijn”, werd onbewoonbaar geacht.
Pres. Thomas Jefferson en degenen die na hem kwamen, stelden zich een “Indiaanse kolonisatiezone” of permanente Indiaanse grens voor, in een noord-zuid-lijn op de westelijke oever van de Mississippi. Velen waren voorstander van deze benadering van “het Indianenprobleem”. Zij geloofden dat het verwijderen van de Indianen naar dat gebied het conflict tussen de oorspronkelijke inheemse bewoners en de Euro-Amerikanen die het continent wilden “beschaven” voorgoed zou oplossen. Blanken zouden ten oosten van de rivier wonen, Indianen ten westen ervan. Een uitgesproken voorstander van een trans-Missippi Indianen zone was de Baptisten missionaris Isaac McCoy, die geloofde dat het gebied uiteindelijk een formeel gebied zou moeten worden, met regering en wetten, voor alle Indianen. Het concept van een Indiaanse zone kreeg vaste vorm tijdens de regering van Pres. John Quincy Adams en ontwikkelde zich later volledig onder leiding van Pres. Andrew Jackson. Een gebied dat werd opgevat als “het Indianenland” werd in 1825 omschreven als al het land dat ten westen van de Mississippi lag. Uiteindelijk zou het Indiaanse land of het Indiaanse Territorium de huidige staten Oklahoma, Kansas, Nebraska, en een deel van Iowa omvatten.
In werkelijkheid was het proces van de Indiaanse Verhuizing al snel na 1800 begonnen door verdragen. Bovendien vluchtten veel stammen eenvoudigweg westwaarts toen de lijn van blanke nederzettingen oprukte in de richting van en vervolgens over de Mississippi rivier. Sommige Cherokee, bijvoorbeeld, waren in de jaren 1810 begonnen naar het westen te trekken, met grote migraties naar west-centraal Arkansas in 1817 naar een gebied dat zij hadden ingeruild voor land in het Zuidoosten. Kort voor het Cherokee-verdrag van 1817 kwam “Lovely’s Purchase” in 1816, en een Osage-verdrag van 1818 maakte in theorie het noordoosten van Oklahoma vrij en voegde het land toe aan het publieke domein. In 1820 stemden de Choctaw in met land tussen de Arkansas en Canadese rivieren en de Rode Rivier, in het huidige Oklahoma.
Intussen staken ook blanken de Mississippi over en begonnen een brede strook die langs de westkant van de Mississippi noord-zuid liep, in te nemen. Al snel was Missouri dichtbevolkt en in 1821 werd het een staat en in 1819 werd Arkansas een territorium. In 1824 werd een westelijke grens voor Arkansas vastgesteld, die alle of een deel van de county’s Craig, Mayes, Delaware, Adair, Cherokee, Sequoyah, Muskogee, Wagoner, Haskell, Le Flore, Latimer, Choctaw, Pushmataha en McCurtain van het huidige Oklahoma omvatte. Het omvatte ook de uit 1816 daterende Osage cessie van Lovely’s Purchase, alsmede een groot stuk land dat in het verdrag van 1820 aan de Choctaw was beloofd. Al in 1816 begonnen blanken zich te vestigen in deze strook land, die in 1820 door Arkansas Territory werd opgenomen in Crawford County, in het noorden, en Miller County, in het zuiden, en die zich zelfs uitstrekte tot in het huidige noordoosten van Texas. In 1827 werd Lovely County gecreëerd uit Crawford County, dat bijna geheel het huidige noordoosten van Oklahoma omvatte, en de zetel werd gevestigd in Lovely Courthouse (Nicksville), later de locatie van Dwight Mission in Sequoyah County.
De Western Cherokee hadden er bezwaar tegen om omringd te worden door blanken en door georganiseerde Arkansas counties. De Choctaw hadden ook bezwaar tegen Miller County en zijn blanke inwoners. In 1825 werd in een nieuw verdrag de oostgrens van de Choctaw aangepast en werd Miller County verkleind. Veel blanken die zich in dat gebied hadden gevestigd, verhuisden nu ten oosten van de nieuwe lijn. In 1828 maakte de federale regering van de situatie gebruik om een nieuw verdrag te sluiten met de Western Cherokees, waarin zij ermee instemden ten westen van de nieuwe lijn te gaan wonen. Lovely County werd opgeheven en de grens tussen Arkansas en het Indian Territory, feitelijk de Choctaw en Cherokee naties, werd in 1828 opnieuw bepaald, in het algemeen langs de huidige grens tussen Oklahoma en Arkansas.
Tijdens de jaren 1820 en 1830 werden tientallen stammen uit het noordoosten, middenwesten en zuidoosten verwijderd door middel van verdragen en onder de Indiaanse Verwijderingswet van 1830, die de president machtigde om stammen te dwingen hun land ten oosten van de Mississippi af te staan. Degenen die dat deden moesten ten westen van de nieuwe blanke nederzettingen worden geplaatst, dat wil zeggen ten westen van de 95e meridiaan. Een handelswet uit 1834 definieerde “het Indiaanse land” verder als al dat deel van de Verenigde Staten ten westen van de Mississippi en niet binnen de staten Missouri, Louisiana of Arkansas Territory, of enig ander georganiseerd gebied. Blanken werden zorgvuldig geweerd uit het gebied, voor de meeste doeleinden, en handel door hen met Indianen werd gereguleerd. Voor juridische doeleinden werd de noordelijke regio (het huidige Kansas) bij Missouri gevoegd en het zuidelijke deel (het huidige Oklahoma) bij Arkansas Territory (na 1836 de staat Arkansas). In 1835 gebruikte Isaac McCoy blijkbaar voor het eerst de woorden “the Indian Territory” in druk.
De Creek, Seminole, en Chickasaw bezweken ook onder de gedwongen migratie. Al deze zuidoostelijke stammen bewoonden daarna het zuidelijke deel van “het Indiaanse Territorium”. Evenzo werden talrijke stammen uit het noordoosten en het noordwestelijk Territorium, waaronder de Kickapoo, Miami, Delaware en Shawnee, overgebracht naar het noordelijk deel, het huidige Kansas. In 1840 was het Indian Territory dus dun bevolkt door inheemse groepen, maar het was geen formeel of georganiseerd gebied.
Hoewel het Congres met de Kansas and Nebraska Act van 1854 die delen van het noordelijke Indian Territory formeel organiseerde in officiële gebieden die later staten werden, omdat het vruchtbare land aantrekkelijk bleek voor blanken. (Kansas trad in 1861 toe tot de Unie en Nebraska in 1867.) Na afloop van de Burgeroorlog werden de Indianen verder naar het zuiden verplaatst naar het deel van het Indian Territory dat nu Oklahoma is. Volksstammen op de vlakten, waaronder de Cheyenne, Arapaho, Comanche, Kiowa en Apache, werden geconcentreerd in reservaten in de westelijke helft van het territorium. In 1889 woonden hier meer dan drie dozijn stammen.
Om de volledige betekenis van de term “Indian Territory” te begrijpen, moet men ook het proces begrijpen waardoor een gebied een territorium werd. Zoals vastgelegd in de wetgeving van de Verenigde Staten, beginnend met de Northwest Ordinance van 1787, konden de bewoners (burgers van de Verenigde Staten), wanneer een specifiek omschreven deel van het ongeorganiseerde federale domein voldoende bevolkt was, bij het Congres een verzoek indienen om territoriale status te verkrijgen. Het Congres nam vervolgens een organieke wet aan, met een wet op de rechten van de bewoners van het gebied, en stelde een driedelige regering in met een benoemde uitvoerende en rechterlijke macht. De inwoners kozen een wetgevende macht. De federale regering had het laatste gezag over territoriale aangelegenheden, en in het Congres zetelde een gekozen territoriale vertegenwoordiger. Het Congres heeft nooit een organieke wet voor het Indian Territory aangenomen, hoewel er enkele maatregelen voor dat doel zijn voorgesteld en één wetsvoorstel is geschreven. Het gebied heeft nooit een formele regering gehad, en het bleef ongeorganiseerd. Daarom was de geografische locatie die gewoonlijk “Indian Territory” wordt genoemd geen territorium.
In de late negentiende eeuw begon de federale regering meer controle te krijgen over gebeurtenissen die zich in Indianenland afspeelden. In maart 1889 werd bij wet een federale rechtbank in Muskogee ingesteld, die de rechterlijke bevoegdheid en jurisdictie overnam die sinds de Handelswet van 1834 werden uitgeoefend door het Westelijk District van Arkansas. De maatregel van 1889 bepaalde voor het eerst de grenzen van het Indian Territory, dat nu officieel was teruggebracht tot een gebied begrensd door Texas in het zuiden, Arkansas en Missouri in het oosten, Kansas in het noorden, en New Mexico Territory in het westen.
Tenna werd dit gebied opnieuw verkleind toen Oklahoma Territory werd gecreëerd uit een deel ervan door de Organieke Wet in mei 1890. Er werd een gouverneur benoemd en een territoriale assemblee met twee kamers en een rechtssysteem werden ingesteld. Als bonafide territorium van de Verenigde Staten zou het Oklahoma Territory in aanmerking komen voor de status van staat als de bevolking voldoende zou groeien en als de leiders de door de federale wet voorgeschreven procedure zouden volgen. In de Oklahoma Territory Organic Act werd het Indian Territory nog nauwkeuriger gedefinieerd, door het te beperken tot iets meer dan de oostelijke helft van de huidige staat. In de Sequoyah Conventie van 1905 probeerden Indiaanse leiders het territoriale proces te omzeilen en een afzonderlijke staat voor het Indian Territory tot stand te brengen. Met de vereniging in 1907 van de Indiaanse naties en Oklahoma Territory als de staat Oklahoma was een afzonderlijk, door Indianen gedomineerd territorium of staat echter niet langer levensvatbaar. In de loop van de twintigste eeuw werd de algemene term “Indian Territory” door historici, genealogen en het publiek gebruikt om de hele regio Oklahoma tijdens de preatehood periode aan te duiden.