Pod koniec XVIII wieku biali osadnicy zaczęli migrować z pierwotnych trzynastu kolonii przez Appalachy na „Zachód”. Na przełomie XIX i XX wieku zaczęli powoli przenosić się do wschodnich części Terytorium Północno-Zachodniego, które zostało utworzone w 1787 roku, oraz do części Starego Południowego Zachodu, czyli Alabamy, Missisipi, zachodniego Kentucky i Tennessee. Postrzegali oni rdzenne ludy, które zamieszkiwały te tereny, jako przeszkodę, którą należy podbić lub popchnąć dalej na zachód.
Stany Zjednoczone wynegocjowały zakup Luizjany w 1803 roku. Chociaż granice pozostały nieokreślone aż do traktatu Adams-Onís z 1819 roku, po 1803 roku rzeka Missisipi nie służyła już jako zachodnia granica kraju. Odkrywcy tej ogromnej amerykańskiej części Trans-Missippi West odkryli, że część wschodnia jest żyzna i nadaje się do zamieszkania. Środkowo-zachodnia część, postrzegana przez niektórych jako „Wielka Amerykańska Pustynia”, była uważana za niezamieszkałą.
Prezydent Thomas Jefferson i ci, którzy podążali za nim, wyobrażali sobie „strefę kolonizacji Indian” lub stałą granicę Indian, w układzie północ-południe na zachodnim brzegu Missisipi. Wielu ludzi opowiadało się za takim podejściem do „problemu indiańskiego”. Wierzyli oni, że usunięcie Indian na ten obszar trwale rozwiąże konflikt między pierwotnymi rdzennymi mieszkańcami a Europejczykami, którzy pragnęli „ucywilizować” kontynent. Biali mieszkaliby na wschód od rzeki, a Indianie na zachód od niej. Jednym z gorących zwolenników strefy Indian nad Missisipi był baptystyczny misjonarz Isaac McCoy, który uważał, że w końcu region ten powinien stać się formalnym terytorium, z rządem i prawami, dla wszystkich Indian. Koncepcja strefy indiańskiej ugruntowała się w czasie administracji prezydenta Johna Quincy Adamsa, a następnie rozwinęła się w pełni pod kierownictwem prezydenta Andrew Jacksona. Region pomyślany jako „kraj Indian” został określony w 1825 roku jako wszystkie ziemie leżące na zachód od Missisipi. Ostatecznie kraj Indian lub Terytorium Indiańskie miało objąć obecne stany Oklahoma, Kansas, Nebraska i część Iowa.
W rzeczywistości proces usuwania Indian rozpoczął się na mocy traktatów wkrótce po 1800 roku. Ponadto wiele plemion po prostu uciekło na zachód, gdy linia białego osadnictwa posuwała się w kierunku rzeki Missisipi, a następnie przez nią. Niektórzy z Czirokezów, na przykład, zaczęli przemieszczać się na zachód w latach 10-tych XIX wieku, a w 1817 roku rozpoczęli wielkie migracje do zachodnio-centralnej części Arkansas, do regionu, który wymienili za ziemię na południowym wschodzie. Krótko przed traktatem z Cherokee z 1817 roku nastąpił „zakup Lovely” w 1816 roku, a traktat z Osage z 1818 roku teoretycznie oczyścił północno-wschodnią Oklahomę i dodał te ziemie do domeny publicznej. W 1820 roku Choctaw zgodzili się przyjąć ziemię pomiędzy rzekami Arkansas i Canadian oraz rzeką Czerwoną, w obecnej Oklahomie.
W międzyczasie biali przekroczyli Missisipi i zaczęli zajmować szeroki pas biegnący z północy na południe wzdłuż jej zachodniej strony. Wkrótce gęsto zaludnione Missouri stało się stanem w 1821 roku, a Arkansas terytorium w 1819 roku. W 1824 roku wyznaczono zachodnią granicę Arkansas, która objęła całość lub część hrabstw Craig, Mayes, Delaware, Adair, Cherokee, Sequoyah, Muskogee, Wagoner, Haskell, Le Flore, Latimer, Choctaw, Pushmataha i McCurtain w obecnym stanie Oklahoma. Włączono do niego również cesję Osage z 1816 roku z Lovely’s Purchase, jak również ogromny kawałek ziemi obiecanej Choctaw w traktacie z 1820 roku. Już w 1816 roku biali zaczęli osiedlać się na tym pasie ziemi, który w 1820 roku został włączony przez Terytorium Arkansas do Hrabstwa Crawford na północy i Hrabstwa Miller na południu, rozciągając się nawet na obecny północno-wschodni Teksas. W 1827 roku hrabstwo Lovely zostało utworzone z hrabstwa Crawford, obejmując prawie całą obecną północno-wschodnią Oklahomę, a jego siedzibą stał się Lovely Courthouse (Nicksville), późniejsza lokalizacja Dwight Mission w hrabstwie Sequoyah.
Zachodni Czirokezi sprzeciwiali się otoczeniu przez białych i zorganizowane hrabstwa Arkansas. Choctaw sprzeciwiali się również hrabstwu Miller i jego białym mieszkańcom. W 1825 roku nowy traktat dostosował wschodnią granicę Choctaw, a hrabstwo Miller zostało zredukowane. Wielu białych, którzy osiedlili się w tym regionie, przeniosło się teraz na wschód od nowej linii. W 1828 roku rząd federalny wykorzystał tę sytuację do zawarcia kolejnego traktatu z zachodnimi Czirokezami, w którym zgodzili się oni przesunąć na zachód od nowej linii. Hrabstwo Lovely zostało zniesione, a granica między Arkansas i Terytorium Indiańskim, a właściwie narodami Choctaw i Cherokee, została ponownie wytyczona w 1828 roku generalnie wzdłuż obecnej granicy Oklahoma-Arkansas.
W latach dwudziestych i trzydziestych XIX wieku dziesiątki plemion północno-wschodnich, środkowo-zachodnich i południowo-wschodnich zostało usuniętych na mocy traktatu i ustawy o usuwaniu Indian z 1830 roku, która upoważniała prezydenta do zmuszenia plemion do odstąpienia swoich ziem na wschód od Missisipi. Ci, którzy to uczynili, mieli zostać umieszczeni na zachód od nowych białych osad, to znaczy na zachód od południka 95. Ustawa o handlu z 1834 roku dalej definiowała „kraj Indian” jako całą część Stanów Zjednoczonych na zachód od Missisipi, poza stanami Missouri, Luizjana, Arkansas Territory lub jakimkolwiek innym zorganizowanym terytorium. Biali byli starannie wykluczeni z tego regionu, dla większości celów, a ich handel z Indianami był regulowany. Dla celów sądowych, północny region (głównie obecne Kansas) został przyłączony do Missouri, a południowa część (głównie obecna Oklahoma) do Terytorium Arkansas (po 1836 r. stan Arkansas). W 1835 roku Isaac McCoy najwyraźniej po raz pierwszy użył w druku słów „Terytorium Indiańskie”.
Creek, Seminole i Chickasaw również poddali się przymusowej migracji. Wszystkie te południowo-wschodnie plemiona zamieszkiwały później południową część „Terytorium Indiańskiego”. Podobnie, liczne plemiona z północnego wschodu i Terytorium Północno-Zachodniego, w tym Kickapoo, Miami, Delaware i Shawnee, zostały usunięte do północnej części, obecnego Kansas. Tak więc do roku 1840 Terytorium Indiańskie było słabo zaludnione przez grupy rdzenne, ale nie było formalnym ani zorganizowanym terytorium.
Jednakże, ponieważ jego żyzna ziemia okazała się pożądana przez białych, na mocy Ustawy o Kansas i Nebrasce z 1854 roku Kongres formalnie zorganizował te części północnego Terytorium Indiańskiego w oficjalne terytoria, które następnie stały się stanami. (Kansas weszło do Unii w 1861 r., a Nebraska w 1867 r.) Po zakończeniu wojny secesyjnej Indianie zostali przeniesieni dalej na południe, do części Terytorium Indiańskiego, która jest obecną Oklahomą. Plemiona równinne, w tym Czejenów, Arapaho, Komanczów, Kiowa i Apaczów, skupiły się w rezerwatach w zachodniej połowie terytorium. Do 1889 roku zamieszkiwało je ponad trzy tuziny plemion.
Aby zrozumieć pełne znaczenie terminu „Terytorium Indiańskie”, należy również zrozumieć proces, w wyniku którego region stał się terytorium. Zgodnie z prawem Stanów Zjednoczonych, począwszy od Ordynacji Północno-Zachodniej z 1787 roku, kiedy konkretnie określona część niezorganizowanej domeny federalnej była wystarczająco zaludniona, jej mieszkańcy (obywatele Stanów Zjednoczonych) mogli złożyć petycję do Kongresu o przyznanie im statusu terytorialnego. Kongres następnie uchwalał akt organiczny, zawierający ustawę o prawach mieszkańców terytorium, i ustanawiał trzyczęściowy rząd z mianowaną władzą wykonawczą i sądowniczą. Mieszkańcy wybierali władzę ustawodawczą. Rząd federalny miał ostateczną władzę nad sprawami terytorialnymi, a w Kongresie zasiadał wybierany przedstawiciel terytorialny. Kongres nigdy nie uchwalił ustawy organicznej dla Terytorium Indiańskiego, chociaż zaproponowano kilka rozwiązań i napisano jedną ustawę w tym celu. Region ten nigdy nie miał formalnego rządu i pozostał niezorganizowany. W związku z tym, położenie geograficzne powszechnie nazywane „Terytorium Indiańskim” nie było terytorium.
Pod koniec XIX wieku rząd federalny zaczął przejmować większą kontrolę nad wydarzeniami zachodzącymi w kraju Indian. W marcu 1889 r. ustawa ustanowiła system sądów federalnych z siedzibą w Muskogee, przejmując władzę sądowniczą i jurysdykcję, która od czasu ustawy o handlu z 1834 r. była sprawowana przez Zachodni Dystrykt Arkansas. Środek z 1889 roku po raz pierwszy określił zamknięte granice Terytorium Indiańskiego, teraz oficjalnie zredukowanego do obszaru ograniczonego przez Teksas od południa, Arkansas i Missouri od wschodu, Kansas od północy i Terytorium Nowego Meksyku od zachodu.
Wkrótce obszar ten został ponownie zredukowany, gdy Terytorium Oklahomy zostało utworzone z jego części na mocy Organic Act w maju 1890 roku. Mianowano gubernatora, utworzono dwuizbowe zgromadzenie terytorialne i system sądowniczy. Terytorium Oklahomy, będące w dobrej wierze terytorium Stanów Zjednoczonych, mogło uzyskać prawa stanowe, jeśli jego populacja wzrosłaby wystarczająco i jeśli jego przywódcy postępowaliby zgodnie z procedurą przewidzianą przez prawo federalne. Akt Organiczny Terytorium Oklahomy jeszcze dokładniej zdefiniował Terytorium Indiańskie, ograniczając je do nieco większej części niż wschodnia połowa obecnego stanu. Podczas Konwencji Sequoyah z 1905 roku przywódcy indiańscy starali się ominąć proces terytorialny i doprowadzić do powstania osobnego stanu dla Terytorium Indiańskiego. Jednak po zawarciu w 1907 roku unii narodów indiańskich i Terytorium Oklahomy jako stanu Oklahoma, oddzielne, zdominowane przez Indian terytorium lub stan nie miało już racji bytu. W XX wieku historycy, genealodzy i opinia publiczna zaczęli używać ogólnego terminu „Terytorium Indiańskie”, aby reprezentować cały region Oklahomy w okresie Prestatehood.