À la fin du dix-huitième siècle, les colons blancs ont commencé à migrer des treize colonies d’origine vers les Appalaches et l' »Ouest ». Au tournant du dix-neuvième siècle, ils ont lentement commencé à s’installer dans les parties orientales du Territoire du Nord-Ouest, qui avait été créé en 1787, et dans certaines parties du Vieux Sud-Ouest, ou de l’Alabama, du Mississippi, et de l’ouest du Kentucky et du Tennessee. Ils considéraient les peuples autochtones qui y résidaient comme un obstacle à conquérir ou à pousser plus à l’ouest.
Les États-Unis ont négocié l’achat de la Louisiane en 1803. Bien que les frontières soient restées indéfinies jusqu’au traité Adams-Onís de 1819, après 1803, le fleuve Mississippi ne servait plus de frontière occidentale à la nation. Les explorateurs de cette énorme portion américaine de l’Ouest trans-mississippien ont révélé que la partie orientale était fertile et habitable. La partie centre-ouest, considérée par certains comme le « grand désert américain », était jugée inhabitable.
Le président Thomas Jefferson et ceux qui l’ont suivi ont envisagé une « zone de colonisation indienne » ou frontière indienne permanente, en un étagement nord-sud sur la rive ouest du Mississippi. De nombreuses personnes ont préconisé cette approche du « problème indien ». Ils pensaient que le déplacement des Indiens vers cette zone résoudrait définitivement le conflit entre les habitants autochtones d’origine et les Euroaméricains qui réclamaient à cor et à cri de « civiliser » le continent. Les Blancs vivraient à l’est du fleuve, les Indiens à l’ouest. Le missionnaire baptiste Isaac McCoy est un fervent partisan de la création d’une zone indienne dans le Trans-Mississippi. Il pense que la région devrait devenir un territoire officiel, doté d’un gouvernement et de lois, pour tous les Indiens. Le concept d’une zone indienne s’est consolidé pendant l’administration du président John Quincy Adams et s’est ensuite pleinement développé sous la direction du président Andrew Jackson. Une région conçue comme « le pays indien » a été spécifiée en 1825 comme étant toutes les terres situées à l’ouest du Mississippi. Finalement, le pays indien ou le territoire indien engloberait les États actuels de l’Oklahoma, du Kansas, du Nebraska et d’une partie de l’Iowa.
En réalité, le processus de déplacement des Indiens avait commencé par des traités peu après 1800. En outre, de nombreuses tribus ont simplement fui vers l’ouest à mesure que la ligne de colonisation blanche avançait vers le Mississippi, puis le traversait. Certains Cherokees, par exemple, avaient commencé à se déplacer vers l’ouest dans les années 1810, avec de grandes migrations dans le centre-ouest de l’Arkansas en 1817, dans une région qu’ils avaient échangée contre des terres dans le sud-est. Peu avant le traité de 1817 avec les Cherokees, il y eut l' »achat de Lovely » en 1816, et un traité avec les Osages en 1818 qui a théoriquement dégagé le nord-est de l’Oklahoma et ajouté les terres au domaine public. En 1820, les Choctaw acceptèrent des terres entre les fleuves Arkansas et Canadien et la rivière Rouge, dans l’actuel Oklahoma.
Pendant ce temps, les Blancs traversèrent également le Mississippi et commencèrent à occuper une large bande allant du nord au sud le long de son côté ouest. Bientôt très peuplé, le Missouri devient un État en 1821 et l’Arkansas un territoire en 1819. En 1824, une frontière occidentale a été tracée pour l’Arkansas, qui comprenait tout ou partie des comtés de Craig, Mayes, Delaware, Adair, Cherokee, Sequoyah, Muskogee, Wagoner, Haskell, Le Flore, Latimer, Choctaw, Pushmataha et McCurtain de l’actuel Oklahoma. Il comprenait également la cession des Osages de Lovely’s Purchase en 1816 ainsi qu’une grande partie des terres promises aux Choctaw dans le traité de 1820. Dès 1816, les Blancs avaient commencé à s’installer dans cette bande de terre qui, en 1820, a été incorporée par le Territoire de l’Arkansas au comté de Crawford, au nord, et au comté de Miller, au sud, s’étendant même jusqu’au nord-est du Texas actuel. En 1827, le comté de Lovely fut créé à partir du comté de Crawford, englobant presque tout le nord-est actuel de l’Oklahoma, et son siège établi à Lovely Courthouse (Nicksville), plus tard l’emplacement de la mission Dwight dans le comté de Sequoyah.
Les Cherokees de l’Ouest s’opposaient à être entourés de Blancs et de comtés organisés de l’Arkansas. Les Choctaw s’opposaient également au comté de Miller et à ses résidents blancs. En 1825, un nouveau traité ajusta la frontière orientale des Choctaw, et le comté de Miller fut réduit. De nombreux Blancs qui s’étaient installés dans cette région déménagèrent à l’est de la nouvelle ligne. En 1828, le gouvernement fédéral profite de la situation pour élaborer un autre traité avec les Cherokees de l’Ouest, dans lequel ils acceptent de se déplacer à l’ouest de la nouvelle ligne. Le comté de Lovely fut aboli et la frontière entre l’Arkansas et le Territoire indien, en fait les nations Choctaw et Cherokee, fut à nouveau arpentée en 1828 généralement le long de la frontière actuelle entre l’Oklahoma et l’Arkansas.
Durant les années 1820 et 1830, des dizaines de tribus du nord-est, du midwest et du sud-est furent déplacées par traité et en vertu de l’Indian Removal Act de 1830, qui autorisait le président à forcer les tribus à céder leurs terres à l’est du Mississippi. Celles qui le faisaient devaient être placées à l’ouest des nouvelles colonies blanches, c’est-à-dire à l’ouest du 95e méridien. Une loi sur le commerce de 1834 définit en outre le « pays indien » comme toute la partie des États-Unis située à l’ouest du Mississippi et ne faisant pas partie des États du Missouri, de la Louisiane ou du territoire de l’Arkansas, ou de tout autre territoire organisé. Les Blancs étaient soigneusement exclus de la région, à la plupart des fins, et leur commerce avec les Indiens était réglementé. À des fins judiciaires, la région nord (essentiellement l’actuel Kansas) était rattachée au Missouri et la partie sud (essentiellement l’actuel Oklahoma) au Territoire de l’Arkansas (après 1836, État de l’Arkansas). En 1835, Isaac McCoy a apparemment utilisé les mots « le territoire indien » pour la première fois dans un document imprimé.
Les Creek, les Seminole et les Chickasaw ont également succombé à la migration forcée. Toutes ces tribus du sud-est ont par la suite habité la partie sud du « Territoire indien ». De même, de nombreuses tribus du Nord-Est et du Territoire du Nord-Ouest, dont les Kickapoo, les Miami, les Delaware et les Shawnee, furent déplacées dans la partie nord, l’actuel Kansas. Ainsi, en 1840, le Territoire indien avait été peuplé, de façon éparse, par des groupes autochtones, mais n’était pas un territoire officiel ou organisé.
Toutefois, parce que ses terres fertiles se sont avérées désirables pour les Blancs, avec la loi de 1854 sur le Kansas et le Nebraska, le Congrès a officiellement organisé ces parties du Territoire indien du Nord en territoires officiels qui sont devenus par la suite des États. (Le Kansas est entré dans l’Union en 1861 et le Nebraska en 1867.) Après la fin de la guerre civile, les Indiens ont été déplacés plus au sud, dans la partie du territoire indien qui est l’actuel Oklahoma. Les tribus des plaines, notamment les Cheyennes, les Arapahos, les Comanches, les Kiowas et les Apaches, furent concentrées dans des réserves dans la moitié ouest du territoire. En 1889, plus de trois douzaines de tribus y résidaient.
Pour comprendre toute la signification de l’expression « le territoire indien », il faut aussi comprendre le processus par lequel une région est devenue un territoire. Comme l’établit la loi américaine, à partir de l’ordonnance du Nord-Ouest de 1787, lorsqu’une partie spécifiquement définie du domaine fédéral non organisé était suffisamment peuplée, ses résidents (citoyens américains) pouvaient demander au Congrès le statut de territoire. Le Congrès adoptait ensuite une loi organique, avec une déclaration des droits des résidents du territoire, et mettait en place un gouvernement tripartite avec des pouvoirs exécutif et judiciaire nommés. Les résidents élisaient une branche législative. Le gouvernement fédéral avait l’autorité ultime sur les affaires territoriales, et un représentant territorial élu siégeait au Congrès. Le Congrès n’a jamais adopté de loi organique pour le Territoire indien, bien que quelques mesures aient été proposées et qu’un projet de loi ait été rédigé à cette fin. La région n’a jamais eu de gouvernement officiel, et elle est restée inorganisée. Par conséquent, l’emplacement géographique communément appelé « Territoire indien » n’était pas un territoire.
À la fin du XIXe siècle, le gouvernement fédéral a commencé à assumer davantage de contrôle sur les événements qui transpirent en pays indien. En mars 1889, une loi a établi un système de tribunal fédéral basé à Muskogee, assumant l’autorité judiciaire et la juridiction qui avaient été exercées depuis la loi sur le commerce de 1834 par le district occidental de l’Arkansas. La mesure de 1889 précisait pour la première fois les frontières fermées du Territoire indien, désormais officiellement réduit à une zone délimitée par le Texas au sud, l’Arkansas et le Missouri à l’est, le Kansas au nord et le Territoire du Nouveau-Mexique à l’ouest.
Cette zone fut à nouveau réduite lorsque le Territoire d’Oklahoma fut créé à partir d’une partie de celui-ci par la loi organique en mai 1890. Un gouverneur fut nommé, une assemblée territoriale à deux chambres et un système judiciaire furent mis en place. Territoire bona fide des États-Unis, le territoire de l’Oklahoma serait éligible au statut d’État si sa population devenait suffisamment importante et si ses dirigeants suivaient le processus prescrit par la loi fédérale. La loi organique du territoire de l’Oklahoma définit encore plus étroitement le territoire indien, le réduisant à un peu plus de la moitié orientale de l’État actuel. Lors de la Convention Sequoyah de 1905, les dirigeants indiens ont cherché à contourner le processus territorial et à faire du territoire indien un État distinct. Cependant, avec l’union en 1907 des nations indiennes et du territoire de l’Oklahoma pour former l’État de l’Oklahoma, un territoire ou un État séparé, dominé par les Indiens, n’était plus viable. Au cours du vingtième siècle, le terme générique « Territoire indien » a fini par être utilisé par les historiens, les généalogistes et le public pour représenter l’ensemble de la région de l’Oklahoma pendant la période de pré-natalité.